コラッツ予想 (Collatz conjecture) その四

前回（↓）の続き。
nazodane.hatenadiary.org

前回のADDVAL>>SHIFTを2進法に直すと以下のようになる。

>>> [bin((0xaaaaaaaaaaaaaaab * ((1 << (i+1)) - 1) &0xffffffffffffffff) >> (i+1)) for i in range(63)]
['0b101010101010101010101010101010101010101010101010101010101010101', '0b0', '0b1010101010101010101010101010101010101010101010101010101010101', '0b0', '0b10101010101010101010101010101010101010101010101010101010101', '0b0', '0b101010101010101010101010101010101010101010101010101010101', '0b0', '0b1010101010101010101010101010101010101010101010101010101', '0b0', '0b10101010101010101010101010101010101010101010101010101', '0b0', '0b101010101010101010101010101010101010101010101010101', '0b0', '0b1010101010101010101010101010101010101010101010101', '0b0', '0b10101010101010101010101010101010101010101010101', '0b0', '0b101010101010101010101010101010101010101010101', '0b0', '0b1010101010101010101010101010101010101010101', '0b0', '0b10101010101010101010101010101010101010101', '0b0', '0b101010101010101010101010101010101010101', '0b0', '0b1010101010101010101010101010101010101', '0b0', '0b10101010101010101010101010101010101', '0b0', '0b101010101010101010101010101010101', '0b0', '0b1010101010101010101010101010101', '0b0', '0b10101010101010101010101010101', '0b0', '0b101010101010101010101010101', '0b0', '0b1010101010101010101010101', '0b0', '0b10101010101010101010101', '0b0', '0b101010101010101010101', '0b0', '0b1010101010101010101', '0b0', '0b10101010101010101', '0b0', '0b101010101010101', '0b0', '0b1010101010101', '0b0', '0b10101010101', '0b0', '0b101010101', '0b0', '0b1010101', '0b0', '0b10101', '0b0', '0b101', '0b0', '0b1']

ようするにこんな感じに単純化できる。

>>> [(lambda t=0b101010101010101010101010101010101010101010101010101010101010101:(t >> i) * ((i&1)^1))() for i in range(63)]
[6148914691236517205, 0, 1537228672809129301, 0, 384307168202282325, 0, 96076792050570581, 0, 24019198012642645, 0, 6004799503160661, 0, 1501199875790165, 0, 375299968947541, 0, 93824992236885, 0, 23456248059221, 0, 5864062014805, 0, 1466015503701, 0, 366503875925, 0, 91625968981, 0, 22906492245, 0, 5726623061, 0, 1431655765, 0, 357913941, 0, 89478485, 0, 22369621, 0, 5592405, 0, 1398101, 0, 349525, 0, 87381, 0, 21845, 0, 5461, 0, 1365, 0, 341, 0, 85, 0, 21, 0, 5, 0, 1]

最後の((((CMPVAL>>SHIFT) - !!((CMPVAL & ((1<>SHIFT))を2進法に直すと以下のようになる。

>>> [bin((lambda shift=i+1, mask=(1<<(i+1))-1:((0x5555555555555555 >> shift) - ((0x5555555555555555&mask) < ((0xaaaaaaaaaaaaaaab*mask) & mask)))&(0xffffffffffffffff>>shift))()) for i in range(63)]
['0b10101010101010101010101010101010101010101010101010101010101010', '0b1010101010101010101010101010101010101010101010101010101010101', '0b101010101010101010101010101010101010101010101010101010101010', '0b10101010101010101010101010101010101010101010101010101010101', '0b1010101010101010101010101010101010101010101010101010101010', '0b101010101010101010101010101010101010101010101010101010101', '0b10101010101010101010101010101010101010101010101010101010', '0b1010101010101010101010101010101010101010101010101010101', '0b101010101010101010101010101010101010101010101010101010', '0b10101010101010101010101010101010101010101010101010101', '0b1010101010101010101010101010101010101010101010101010', '0b101010101010101010101010101010101010101010101010101', '0b10101010101010101010101010101010101010101010101010', '0b1010101010101010101010101010101010101010101010101', '0b101010101010101010101010101010101010101010101010', '0b10101010101010101010101010101010101010101010101', '0b1010101010101010101010101010101010101010101010', '0b101010101010101010101010101010101010101010101', '0b10101010101010101010101010101010101010101010', '0b1010101010101010101010101010101010101010101', '0b101010101010101010101010101010101010101010', '0b10101010101010101010101010101010101010101', '0b1010101010101010101010101010101010101010', '0b101010101010101010101010101010101010101', '0b10101010101010101010101010101010101010', '0b1010101010101010101010101010101010101', '0b101010101010101010101010101010101010', '0b10101010101010101010101010101010101', '0b1010101010101010101010101010101010', '0b101010101010101010101010101010101', '0b10101010101010101010101010101010', '0b1010101010101010101010101010101', '0b101010101010101010101010101010', '0b10101010101010101010101010101', '0b1010101010101010101010101010', '0b101010101010101010101010101', '0b10101010101010101010101010', '0b1010101010101010101010101', '0b101010101010101010101010', '0b10101010101010101010101', '0b1010101010101010101010', '0b101010101010101010101', '0b10101010101010101010', '0b1010101010101010101', '0b101010101010101010', '0b10101010101010101', '0b1010101010101010', '0b101010101010101', '0b10101010101010', '0b1010101010101', '0b101010101010', '0b10101010101', '0b1010101010', '0b101010101', '0b10101010', '0b1010101', '0b101010', '0b10101', '0b1010', '0b101', '0b10', '0b1', '0b0']

ようするにこんな感じに単純化できる。

>>> [(lambda t=0b10101010101010101010101010101010101010101010101010101010101010:t >> i)() for i in range(63)]
[3074457345618258602, 1537228672809129301, 768614336404564650, 384307168202282325, 192153584101141162, 96076792050570581, 48038396025285290, 24019198012642645, 12009599006321322, 6004799503160661, 3002399751580330, 1501199875790165, 750599937895082, 375299968947541, 187649984473770, 93824992236885, 46912496118442, 23456248059221, 11728124029610, 5864062014805, 2932031007402, 1466015503701, 733007751850, 366503875925, 183251937962, 91625968981, 45812984490, 22906492245, 11453246122, 5726623061, 2863311530, 1431655765, 715827882, 357913941, 178956970, 89478485, 44739242, 22369621, 11184810, 5592405, 2796202, 1398101, 699050, 349525, 174762, 87381, 43690, 21845, 10922, 5461, 2730, 1365, 682, 341, 170, 85, 42, 21, 10, 5, 2, 1, 0]

あまり最適化に使える気はしないけど多倍長の時に偶数と奇数それぞれで上位ビット消すだけで済むのは利点かな？