магический код

[avva]

Забавный комментарий в одном из файлов исходников пакета Judy:


// Test if Word has any of the 4 bytes == '\0':
//
// This arcane code takes advantage of the CPU having a fast barrel shifter and
// a carry bit. Doug stole this code from elsewhere, and we know it works, but
// we really can't explain why.

#define NOZEROBYTE(Word) \
((((((Word) - 0x01010101) | (Word)) ^ (Word)) & 0x80808080) ? 0 : 1)

Кто возьмётся объяснить? ;) У меня глаза слипаются и думать совершенно нет сил, я отправляюсь спать.

Update: Всё-таки подумал. Просто на самом деле. Но красиво.

Comments

[ex-ilyavinar899.livejournal.com]

y = (((x-0x01010101) | x) ^ x) & 0x80808080

Consider one of the bytes of x. If it is not zero, then at least one of its bits is one; let's say that bit j is the least significant one. When we subtract 0x01 from it, bits 0..j-1 will be set to one, and bit j will be set to zero. When we OR it with x, bits 0..j will be set to one. When we XOR it with x, bits j..7 will be set to zero, and 0..j-1 will be set to one. So if the word contains no zero bytes, the result will not have any byte where bit 7 is set to one.

If the word contains a zero byte, then for the highest byte when we subtract 0x01 from it, it will be 0xFF. When we OR it with x, it will be 0xFF. When we XOR it with x, it will still be 0xFF. Its bit 7 will be set.

[malaya-zemlya.livejournal.com]

Ага. Эта штука была в старом Dr.Dobbs Journal-е

Другой вариант на ту же тему - со вступительного интервью на фирму Eidos:

c=0
while (x)
{
x&=x-1;
c++;
}

[bolk.livejournal.com]

Красивее
for (c=0; x; c++) x&=x-1

[(Anonymous)]

Гораздо интереснее решать такие задачи, чем понимать уже известное решение (правда для этого сначала должна возникнуть необходимость такую задачу решить). Вот я как-то неправильно понял условие одной такой задачи, в результате чего решил сначала одну, а потом другую (точнее, она уже была решена не мной, я только повторил решение). Привожу обе:
1. (Наиболее коротким способом) определить в каком из двух слов младший ненулевой бит младше.
А сначала я решал такую:
2. (Наиболее коротким способом) произвести сравнение двух слов от младших битов к старшим.
Если интересно, позже дам свои решения.

--
б. мучачо

[ullr.livejournal.com]

1. #define LEAST_BIT(z) (z-((z-1)&z)
if ( LEAST_BIT(x) > LEAST_BIT(y) )
//bla-bla-bla

[(Anonymous)]

Хороший вариант, но можно (http://www.livejournal.com/users/avva/796046.html?thread=9741198#t9741198) на две операции меньше (за ассемблер, правда, не скажу).

Re:

[avva.livejournal.com]

Решать мне лень, честно говоря. А решения дайте, интересно.

[(Anonymous)]

1. Это решение автора задачи (не моё):
bool Compare(DWORD n1, DWORD n2)
{
return (n1 ^ (n1 - 1)) <= (n2 ^ (n2 - 1));
}

2. Ну а это моё решение задачи № 2 (неправильно понятой №1):
bool Compare2(DWORD n1, DWORD n2)
{
DWORD mask = ((n1 ^ n2) - 1) ^ (n1 ^ n2);
return (n1 & mask) <= (n2 & mask);
}

Disclaimer: код не отлажен (хоть и проверен на бумажке) ;)