さて、どこかで見たネタ。なんとなく、『夏休み学生実習』の演習問題っぽかったので、いままで待っていた。

もうそろそろ、いいよね。

.

2^a であることが保障されている値 x から a を求めるのだそうだ。

こういう問題は何も考えずに「Hacker's Delight」。Chapter 5 にもろ「COUNTING BITS」という章がある。

x = 2^a で　1≦a≦9 が保障されていると言うことは、
x-1 = (2^a - 1) = (2^(a-1) + 2^(a-2) + .... + 2¹ + 2⁰ ) / (2-1)

ということで x-1 には「a個の 1 が立っている」事が判る。

y=x-1 として、「yには何個ビットが立っていますか?」というのが問題なのだ。だからわざわざ a は　1からスタートしている。

.

a が最大 9 だということは 12bit分だけ考慮すればよい、ということだ。とりあえず16bit分のレジスターがあると考えよう。

y = (y & 0x5555) + ((y >> 1) & 0x5555);
y = (y & 0x3333) + ((y >> 2) & 0x3333);
y = (y & 0x0F0F) + ((y >> 4) & 0x0F0F);
y = (y & 0x00FF) + ((y >> 8) & 0x00FF);

これで y には「yに何個のビットが立っていたか」…つまり a の値が入った事になる。

.

多分わかっている人には「あーーーー!! そうそう」ネタなのだが、知らなかった人にはえぇぇええええっ?!????だろう。

この驚きがあるから、技術者と言う商売は辞められない。