забавный код на C

[avva]

Эту запись имеет смысл читать только тем, кто знает язык программирования C.

Мне его выдал форчун, уже не в первый раз, и я решил на этот раз записать. Если вам
нечего делать, разгадывайте, что делает этот код с 32-битным числом n:

n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa);
n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc);
n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0);
n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00);
n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);


Update: 37 нашёл отличную ссылку по теме.

Comments

[(Anonymous)]

Not seeing assembly, did not undertand how your variant can be faster. Well, you have extra call to stroul() in loop in assembly for avva's variant.

Here are the numbers in seconds on Intel box:

avva - 0.43
37 - 10.13
oxfv - 1.23 / 0.55 with loop unroll
oxfv/byte table - 0.48 / 0.22 with loop unroll

[37.livejournal.com]

strtoul - äà ÿ, êàê ÿ äóìàþ, ïðîñòî íå îòðåçàë åãî â àââèíîì êîäå. Õîòÿ, êîíå÷íî, ïðîâåðþ åùå ðàç, íî äåëàë ýòè ïðèìåðû èç îäíîãî øàáëîíà. Ê ñîæàëåíèþ, êîä îñòàëñÿ ó ìåíÿ íà ðàüîòå, çàíîâî íàáèâàòü åãî íå áóäó, ìîãó ïîñëàòü Âàì äëÿ ïðîâåðêè òîëüêî â ïîíåäåëüíèê (íà òîò ñëó÷àé, åñëè Âû ñîìíåâàåòåñü â äîáðîñîâåñòíîñòè ìîèõ óïðàæíåíèé:-))).  ñâîþ î÷åðåäü, ìîæåòå ïðèñëàòü ìíå ñâîè ïðèìåðû äëÿ ïðîâåðêè, íî ñðàçó ñêàæó, ÷òî ðàçíèöà áîëåå ÷åì â 20 ðàç(!) è, îñîáåííî, âî âòîðîì ñëó÷àå â 20 ðàç âûçûâàåò áîëüøîå ñîìíåíèå è ïîäîçðåíèå â ÷èñòî ìåòîäè÷åñêîé îøèáêå. Íå î÷åíü ïîíÿòíî Âàøå íåâåðèå â ñàìó âîçìîæíîñòü ýòîãî - óæ íå ñ÷èòàåòå ëè Âû, ÷òî êîëè÷åñòâî ñòðîê Ñ-êîäà îäíîçíà÷íî êîððåëèðóåò ñ äëèíîé åãî âûïîëíåíèÿ? Òîãäà åùå ðàç ïîñìîòðèòå íà àññåìáëåðíûé êîä (î strtoul, ðàçóìååòñÿ, çàáóäüòå).

[(Anonymous)]

20 times difference indeed sounds excessive. I just checked and looks like in attempt to optimize your code I slowed it down twice. From quick look at the assembly you gave, difference should be 5-10 times.

Reason is that for branches Intel (and generally all modern CPUs) takes a performance penalty due to pipeline stalls and flushes. Also in your main
loop there is 1 instruction between branches where as potentially Intel can execute several instructions simultaneosly.

As for assembly from avva's code, it's linear and the only possible problem I see with it is that on Pentium IV shifts are slower and have higher latency than ALU operations. But then, there is 7 assembly shifts in his variant and 16 in yours.

You are right in a sense that this all is mostly compiler problem. Given your code I don't see any reason why compiler shouldn't be able to generate code which executes at most 2-3 times slower than
original tricky implementation.

[37.livejournal.com]

Êàê çàêëþ÷åíèå. Âû ïðàâû: îñíîâíîå çëî - â branch. Èíòåë âûïîëíÿåò ýòî î÷åíü ìåäëåííî, ÷åãî ÿ, êîíå÷íî, íå ó÷åë â îöåíêàõ (ïðî ñåáÿ ñ÷èòàë, ÷òî if(...) something ñòîèò î÷åíü ãðóáî ãîâîðÿ â ñðåäíåì 1.5 îïåðàöèè, à îêàçàëîñü - â ñðåäíåì áîëüøå 2-õ, ò.å., êîãäà ñðàâíåíèå - èñòèíà, âûïîëíåíèå èäåò áûñòðåå, ÷åì êîãäà ïðîïóñêàåòñÿ ñëåäóþùèé îïåðàòîð). Êàê ïàðàäîêñ, ÿ äëÿ ïðèìåðà ïîñòðîèë âîîáùå ÷èñòî ëèíåéíûé äëèíþùèé êîä ïî òèïó:
n1 |= (n & 0x800000000) >> 31;
.....
È ýòîò îãðîìíûé (è â àññåáëåðå as well) êîä âûïîëíÿëñÿ âñåãî â 2.5 ðàçà ìåäëåííåå, ÷åì êîä àââû, è íàìíîãî áûñòðåå ÷åì åñëè èñïîëüçîâàòü êîìàíäû òèïà
if(n & 0x800000000) n1 |= 0x00000001;
 ïîíåäåëüíèê ïîïðîáóþ ðàäè èíòåðåñà íà íåñêîëüêèõ äðóãèõ òèïàõ ïðîöåññîðîâ.
Çà ñèì ïðîùàþñü, èáî è òàê íàïëîäèë óæå íåèìîâåðíîå êîëè÷åñòâî òåêñòà â ÷óæîì æóðíàëå.