ABC081B - Shift only を除算、剰余算、右ビットシフト、ビット論理積なしで解いた

以前投稿した記事で以下のようなことを書きました。

2で割れる回数は「立っているビットのうち一番下位のものより下位に連続する0の数」を数えればいいと思います。

const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )
const [ n, tmp ] = input.split( "\n" )
const a = tmp.split( " " ).map( v => parseInt( v, 10 ) )

//最大操作回数。初期値は31より大きければどんな数値でも大丈夫です。
let count = Number.POSITIVE_INFINITY

for ( let c of a ) {

 //「立っているビットのうち一番下位のものより下位に連続する0」の部分だけビットを立てます。
 c ^= c - 1
 c >>>= 1

 //立っているビットの数を数えます。
 c = ( c >>> 1 & 0x55555555 ) + ( ( c & 0x55555555 ) >>> 0 )
 c = ( c >>> 2 & 0x33333333 ) + ( ( c & 0x33333333 ) >>> 0 )
 c = ( c >>> 4 & 0x0F0F0F0F ) + ( ( c & 0x0F0F0F0F ) >>> 0 )
 c = ( c >>> 8 & 0x00FF00FF ) + ( ( c & 0x00FF00FF ) >>> 0 )
 c = ( c >>> 16 & 0x0000FFFF ) + ( ( c & 0x0000FFFF ) >>> 0 )

 if ( count > c ) {
   count = c
 }

}

console.log( count )

このアルゴリズムのキモはc - 1で下位に連続する0の部分のビットを立てて1にし、それと元の値で排他的論理和を取るc ^= c - 1で上位のビットを全て0にすることです。
こうすることで2の倍数以外の因数を無視できます。
しかし、この時点では除算もビットシフトも使っていません！
ということは、これを改良すれば除算もビットシフトも用いずに2で割れる回数を計算できそうです。

割れる回数は事前計算する

問題の制約では与えられる整数は1以上10の9乗以下となっています。
30回2で割れる数は1073741824でこれは10の9乗を超えるので、2で割れる回数の最大は536870912の29回です。
よって割れる回数のパターンは0〜29回までの30通りになります。
同様に、c ^= c - 1の計算結果は2進数表記で以下の30通りです。

1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111111
111111111111111111111111
1111111111111111111111111
11111111111111111111111111
111111111111111111111111111
1111111111111111111111111111
11111111111111111111111111111
111111111111111111111111111111

これをJavascriptで実装したものが以下になります。

const calculated = Array( 30 ).fill( 2 ).map( ( v, i ) => ( v << i ) - 1 )

割れる回数はどこに行ったのでしょうか？
実は配列のインデックスが2で割れる回数になります。
これでArray.prototype.indexOfを使うことで割れる回数の取得が可能になりました。

解法

割れる回数の事前計算ができたので、除算や右ビットシフトなしに問題を解くことが出来ました。

const calculated = Array( 30 ).fill( 2 ).map( ( v, i ) => ( v << i ) - 1 )
const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )

const lines = input.split( "\n" )
const N = parseInt( lines[ 0 ], 10 )
const A = lines[ 1 ].split( " " ).map( v => parseInt( v, 10 ) )

const count = Math.min( ...A.map( c => calculated.indexOf( c ^ c - 1 ) ) )
console.log( count )

おわり

以上！
「一見何をやってるのかわからない感」が増しましたね。
使い所あるのかこれは……？