?

Log in

магический код - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

магический код [июн. 3, 2003|03:30 am]
Anatoly Vorobey
[Настроение |sleepysleepy]

Забавный комментарий в одном из файлов исходников пакета 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:
From: ex_ilyavinar899
2003-06-02 06:13 pm
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.
(Ответить) (Thread)
[User Picture]From: malaya_zemlya
2003-06-02 10:33 pm
Ага. Эта штука была в старом Dr.Dobbs Journal-е

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

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

(Ответить) (Thread)
[User Picture]From: bolk
2003-06-02 11:45 pm
Красивее
for (c=0; x; c++) x&=x-1
(Ответить) (Parent) (Thread)
From: (Anonymous)
2003-06-03 03:38 am
Гораздо интереснее решать такие задачи, чем понимать уже известное решение (правда для этого сначала должна возникнуть необходимость такую задачу решить). Вот я как-то неправильно понял условие одной такой задачи, в результате чего решил сначала одну, а потом другую (точнее, она уже была решена не мной, я только повторил решение). Привожу обе:
1. (Наиболее коротким способом) определить в каком из двух слов младший ненулевой бит младше.
А сначала я решал такую:
2. (Наиболее коротким способом) произвести сравнение двух слов от младших битов к старшим.
Если интересно, позже дам свои решения.

--
б. мучачо
(Ответить) (Thread)
[User Picture]From: ullr
2003-06-03 02:02 pm
1. #define LEAST_BIT(z) (z-((z-1)&z)
if ( LEAST_BIT(x) > LEAST_BIT(y) )
//bla-bla-bla


(Ответить) (Parent) (Thread)
From: (Anonymous)
2003-06-03 10:05 pm
Хороший вариант, но можно (http://www.livejournal.com/users/avva/796046.html?thread=9741198#t9741198) на две операции меньше (за ассемблер, правда, не скажу).
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2003-06-03 04:00 pm

Re:

Решать мне лень, честно говоря. А решения дайте, интересно.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2003-06-03 09:55 pm
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: код не отлажен (хоть и проверен на бумажке) ;)
(Ответить) (Parent) (Thread)