okkyの日記： 2^a を与えられたときに a を求める(ただし 1≦ a ≦9)

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

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

.

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 の値が入った事になる。

.

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

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

別解

[t-nissie (8647)]

if (x.eq.1) return 0
if (x.eq.2) return 1
if (x.eq.4) return 2
if (x.eq.8) return 3
（中略）
if (x.eq.512) return 9
stop 'illegal x'

こっちの方が見通しがよいしx=1に対応できますが、
ぼくがなにか勘違いしているのかな。

--
love && peace && free_software
t-nissie

Re:別解

[TarZ (28055)]

　合っていると思います。が、元々の問題の要請が、なるべくループやlogを使わない（でもってできればステップも減らしたい）なのです。
　ということで、1, 2, 4, ... 512 の完全最小ハッシュを作る、というのが最小の解のようです。（乗算x1, ビットシフトx1, インデックスメモリ参照x1）

Re:別解

[okky (2487)]

多分その解は『何をもって最小と言うのか』に強く依存していると思う。
例えば、ハッシュテーブルを作るための計算量が丸々無視されている。

メモリをいくら使っても構わないのであれば 0..512 の 513エントリの表を持てばいいだけです。そういう意味ではTable Lookupは最後の手段だと思いますね。

.

いや、実生活で本当にこういう問題があるなら話は別だけどさ。誰がどう見ても『学生演習』の類だもの。こういうのは趣味丸出しにしないと＼(^o^)／

--
fjの教祖様

Re:別解

[t-nissie (8647)]

> ということで、1, 2, 4, ... 512 の完全最小ハッシュを作る、というのが最小の解のようです。

これが題意か。納得。しかし、

>（乗算x1, ビットシフトx1, インデックスメモリ参照x1）

ここまで小さくできないです。これがぼくの限界か（32bit限定だし）：

#define func1to9(x) ( 9 - (2271560481U*(x>>1)*(x>>1)*(x>>1)*(x>>1) >> 28) )
#define func0to8(x) ( 8 - (2271560481U*x*x*x*x >> 28) )

0≦a≦8のほうが綺麗に書けるから、わざわざ1≦a≦9にしているのを使っていないのか…

--
love && peace && free_software
t-nissie

Re:別解

[TarZ (28055)]

　今見つかっている最小のハッシュ関数はこれですね。乗算とシフト、11バイト+終端1バイトのテーブルを使います。どうやって求めたのかは私も解りません。

"\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28];

Re:別解

[okky (2487)]

ロジックをちゃんと追わずに、問題だけ読みましたね?
ちゃんとロジックを追えば、私が書いた解もx=1に対応している事が判ったはずです。

それはともかく。

.

もちろん、このコードは正しいですし、おそらく学生演習などでは90%ぐらいはこのコードを書いてくるでしょう。でも、私が担当ならば、この解に対する点は60点です(あ、一応単位取得最低点数が60点として、ね)。

このコードは見通しがよいとは到底言えません。正確には「メンテナンス性のある見通し」は絶無だ、と評価します。一方で試行錯誤の後もありません。どちらかがあれば、残り40点を付与するのですが。
.

if/else (含む switch/case)による方法であれ、hash table 法であれ、
『あれが来たら、これを返せ』
的な実装はコードの中に、何ゆえにそのような戻り値を返すのかが絶対記述されません。

コメントのような「実行されるロジックと無関係な」部分に記述しても、『言語として読めない人たち』『能力として読まない人たち』『ロジックとの乖離を気にしない人たち』によって見る見るうちに、実装と記述が乖離してしまい、なおかつそれを自動的に検出する方法がありません。

つまり、その手の「あれが来たら、これを返せ」的記述方法はコードの妥当性確認ができない、という意味においてメンテナンス性が皆無なのです。その一方で、「例外として…」的な記述はしやすい。余計な if 文を追加してもわからないでしょう?そして、こういう所から、

• コメントとロジックの乖離
• if/then/else のネストによって論理破綻を起こしたコード

という2大バグの温床が発生します。

プログラムと言うのは猿にメンテナンスの真似事が出来るように作ってはいけません。猿はメンテナンスと称して破壊活動を行っているだけであり、なおかつ短期的にはそれが動いたりすると、後に甚大な被害をもたらすからです。しかし、かといって意味も無く可読性だけを落とすのも論外です。

私はHacker's Delight [geocities.jp]を全てのプログラマが読むべき本としていますが、それは知識を必要とするが、可読性の高い、猿が破壊行動を行えば即座にその事が露呈する…つまり本当の意味でメンテナンス性の高いコードをこそ、プログラマは書くべきだ、と思っているからです。

--
fjの教祖様

Re:別解

[t-nissie (8647)]

いや、ちゃんとロジックも追いましたが、

> 2**a であることが保障されている値 x から a を求めるのだそうだ。
> x = 2**a で　1≦a≦9 が保障されていると言うことは、

の２つがあるかぎり、ifで書いても（書いた方が）見通しはよいし
if/then/elseのネストは起きないわけで。

逆にぼくはこの２つの保証が信じられるほどナイーブではないんで、
不正な値が来たら止まるようなプログラムを作って欲しいです。

--
love && peace && free_software
t-nissie

Re:別解

[okky (2487)]

いや、ちゃんとロジックも追いましたが

おいおい(；一_一)
ならばx=1 の場合は a=0なのだから「問題の段階でこない」か、「a=0が返る」のどちらであっても正しくなる事が判るではないか。

不正な値が来たら止まるようなプログラムを作って

それは逆の意味でナイーブ過ぎるな。
むやみやたらと止まられるのも困る。

ちなみに。top bit 以外を全部落とす方法はある。問題の定義を変えるのならば、そちらの方がよろしかろう。

--
fjの教祖様