Multiplication Table (Alice In Wonderland) - ビット演算

どんな問題？

Multiplication Table
http://www.checkio.org/mission/multiplication-table/

新しい掛け算の定義を作った。下記に従って計算せよ。

• 数字を二進数に変換する。（先頭の0は除去する。）
• 最初の数を縦に、2番目の数を横に並べ、AND, OR, XORの3つの表を作る。
• 表の各セルで、それぞれAND, OR, XORの演算を行う。
• ビット演算の結果を、行ごとに二進数から十進数に変換する。
• 各行の和を計算し、3つの表の合計値を求める。

ひさびさに問題文の意味がわからなくて苦労した。
例題にあるように「4x6=」の場合は、まず4を100に変換して縦に並べ、6を110に変換して横に並べて、表を作る。

X	1	1	0
1
0
0

これを、AND, OR, XOR の3つ作って、それぞれビット演算を行い、その結果を、各行ごとに二進数から十進数に変換する。
例えば、ANDの表は以下のようになり、赤い部分(110)を十進数にすると6となる。

X	1	1	0	十進数
1	1	1	0	6
0	0	0	0	0
0	0	0	0	0

ANDの各行の和は、6+0+0=6。同様にして、AND,OR,XORの表の合計値を求める。

例題：

checkio(4, 6) == 38
checkio(2, 7) == 28
checkio(7, 2) == 18

ところで、

numbers to binary representation without trailing zeroes.

とあるので、後ろの0を除去するのかと思ったら、先頭の0を除去すればいいようだ。（でもtrailingって後ろじゃないの？）

どうやって解く？

まず、

X	1	1	0	十進数
1	1	1	0	6

この部分はまとめて計算できそうだ。firstのビット'1'をsecondのビット数(3個)並べたら'111'となる。0b111と0b110でANDを取れば、0b110(6)となる。

また、AND,OR,XORの計算も一ヶ所にまとめてしまおう。

def checkio(first, second):
    first_bin = format(first, 'b')
    second_bin = format(second, 'b')

    result = 0
    for b in first_bin:
        n = int(b * len(second_bin), 2)
        result += n & second
        result += n | second
        result += n ^ second
    return result

もっと短くできそうだ。

def checkio(first, second):
    second_len = len(format(second, 'b'))
    first_nums = [int(d * second_len, 2) for d in format(first, 'b')]
    return sum((n & second) + (n | second) + (n ^ second) for n in first_nums)

http://www.checkio.org/mission/multiplication-table/publications/natsuki/python-3/first/
これでクリア。問題文はややこしかったが、中身はわりと簡単。

他の人の答え

int.bit_length()メソッドなんてあったのか。知らなかった。テストしてみる。

>>> for i in range(8): i, bin(i), i.bit_length()
...
(0, '0b0', 0)
(1, '0b1', 1)
(2, '0b10', 2)
(3, '0b11', 2)
(4, '0b100', 3)
(5, '0b101', 3)
(6, '0b110', 3)
(7, '0b111', 3)

これなら、len(format(second), 'b') とする代わりに second.bit_length() でOK

AND, OR, XORを使わずに計算している解答も多かった。例えばこれ。

def checkio(a, b):
    c = bin(a)[2:]
    return 2 * (c.count("1") * (2**(len(bin(b)) - 2) - 1) + c.count("0") * b)

http://www.checkio.org/mission/multiplication-table/publications/madmanbob/python-3/first/

どうやって計算しているのか、よく分からなかったので一つずつ見ていく。
まず、(x&y)+(x|y)+(x^y)は、次のような値になる。

x	y	AND	OR	XOR	AND+OR+XOR
0	0	0	0	0	0
0	1	0	1	1	2
1	0	0	1	1	2
1	1	1	1	0	2

つまり、(x&y)+(x|y)+(x^y) を S とおくと、

• x=0のとき、y=0 なら S=0、y=1 なら S=2、つまり S=y*2
• x=1のとき、常に S=2

となる。

つぎに、(2**(len(bin(b)) - 2) - 1) は、 2**b.bit_length()-1 と置き換えるとわかりやすい。これは、bのすべてのビットを1にした数字となる。
だから、aを二進数表記して、'0'と'1'の数を数えて、

• '0'の数 × b × 2
• '1'の数 × (2**b.bit_length()-1) × 2

の合計が答えとなる。

例えば「4x6=」なら、4は0b100なので、'0'は2個、'1'は1個ある。
6(0b110)のすべてのビットを1にすると7(0b111)なので、

• 2 × 6 × 2 = 24
• 1 × 7 × 2 = 14

合計は 24+14=38 となる。
なんか、わかったようなわからないような。

別解

上の(x&y)+(x|y)+(x^y)の表を書いていて、思いついたのだが、AND+OR+XORはOR*2であることがわかる。だから

def checkio(first, second):
    first_nums = [int(d * second.bit_length(), 2) for d in format(first, 'b')]
    return sum((n | second) * 2 for n in first_nums)

これでもいける。