[ amidar @ 01.08.2001. 02:40 ] @
--- A riddle ---

The code cited below is from an usenet article posted in 1993 in comp.lang.c.
The original author is Doug Merrit ([email protected]). I've reformatted the
header lines but otherwise not touched the article.

From moppi!sunflower.sub.org!transtec.de!xlink.net!howland.reston.ans.net!
vixen.cso.uiuc.edu!sdd.hp.com!decwrl!decwrl!csus.edu!netcom.com!doug
Thu Aug 05 21:30:09 MSZ 1993
Newsgroups: comp.lang.c
Path: moppi!sunflower.sub.org!transtec.de!xlink.net!howland.reston.ans.net!
vixen.cso.uiuc.edu!sdd.hp.com!decwrl!decwrl!csus.edu!netcom.com!doug
From: [email protected] (Doug Merritt)
Subject: puzzle: code found in Huge Program From Hell
Message-ID: <[email protected]>
Organization: Netcom Online Communications Services (408-241-9760 login: guest)
References: <[email protected]> <[email protected]>
<[email protected]>
Date: Tue, 3 Aug 1993 16:30:55 GMT
Lines: 31

Here's a fun puzzle for y'all. I was reading through 2000 lines of
uncommented dense code that's part of an even larger complex and ancient
body of code (the proverbial Huge Program From Hell :-) and found
the following gem...after puzzling over it for a bit I realized that
it was a rather clever algorithm, one that I'll doubtless find use
for in the future:

function (unsigned int value)
{
int count;

for (count=0; value; count++)
value &= (value - 1);

return (count);
}

This was actually embedded in a huge function, but never mind that.

10 points to anyone who already knows this algorithm.

Also 10 points to anyone who figures out what it does within 2 minutes. Bonus points if you can prove that it is correct (modulo any typos I may have introduced :-) Yet extra bonus points for comparing it to the other three well known algorithms for doing the same thing.

30 points to anyone who can apply the general idea to solve a completely
different problem (it is suggestive but I haven't found another application
yet, myself).
Doug
--
Doug Merritt [email protected]
Professional Wild-eyed Visionary Member, Crusaders for a Better Tomorrow




--- The C ?: operator ---

The ?: operator is very useful in writing cryptic code in C. If you combine
this operator with a missing knowledge of the representation of boolean values in C, you will get interesting results.
The stuff below is from a big (and buggy) library that is in use somewhere (no details, sorry:-).

if (LotIndex < usNumLots?(LotIndex >= 0?1:0):0) { memcpy(pUnitId, pCurrentRun->lot[LotIndex].track_num, LEN_TOOL_TRACK);
}


Three big cheers for you if you can decide in less that 10 seconds under which conditions the code inside the if clause is executed.
[ duke @ 01.08.2001. 05:05 ] @
Resenje prve zagonetke:

Funkcija vraca broj jedinica u binarnom zapisu argumenta.

Dokaz:
Sta se desava sa value u svakom prolasku korz petlju? Ako je value neparan,
jedinica na mestu najmanje tezine se brise, a sve ostale cifre ostaju nepromenjene.
npr. value = 79 = 1001111b
value & (value-1) = 1001111 & 1001110 = 1001110

Ako je value paran, gubi se prva jedinica s desne strane, jer se sve nule desno od nje pretvaraju u jedinice pri oduzimanju za 1, a ona sama u nulu, sto se sve zajedno
andovanjem ponistava. Znam da zvuci jako konfuzno, pa zato evo primer:

value = 88 = 1011000b
value &(value-1) = 1011000 & 1010111 = 1010000

Dakle u svakom prolasku kroz petlju value ostaje bez jedne jedinice u svom binarnom zapisu. Kako je uslov za izlazak iz petlje upravo value, to ce se petlja izvrteti upravo onoliko puta koliko value ima jedinica, a to je bas ono sto ova funkcija vraca
QOD

Inace alogoritam je sam po sebi dovoljno lud, a ono sto je jos ludje je kako se jednostavno moze zapisati u C-u. Ovako eleganto bi mogao izgledati jos samo u masincu i nijednom drugom jeziku. Ko god da je izmislio C (K&R) svaka mu (im) cast.

Sto se tice druge zagonetke ona je malo manje zanimljiva, ali sve u svemu resenje je:
usNumLots > LotIndex >= 0

Mrzi me sad da objasnjavam zasto ...
[ amidar @ 01.08.2001. 08:51 ] @
Ma, ovo sam postovao da bih podelio sa vama, no lepo od tebe sto objasni :-)