4の累乗に対して倍数を数えます。

Question

与えられた数値nを与えられたら、この数が与えられた数よりも4のべき乗の倍数であることを効率的に調べる必要があります。例について

：

• 16は4の倍数であり、及び16、その結果は、2
• 64 4、16、64の倍数であるであろう、その結果は次のようになり
• 256 3は4の倍数、16、64、及び256であるので、結果は、
• 14 4. 4のいずれかの電力の倍数ではないであろう、その結果は次のようになり0
• 35は4の累乗の倍数ではないため、結果は0になります。

ビット単位の操作が推奨されていますが、これは非常にタイトなループであり、効率的である必要があるボトルネックの内側にあります。現時点では私のコードは明白な答えですが、私はあまりの手順で結果を把握することができますより多くの数学的な何かがあると信じてする必要があります。

power = 4; 
while (power < n) { 
    result += !(n & (power - 1)); 
    power *= 4; 
} 

Answer 1

対数を使用できます。 "fast log2 C++"をすばやくGoogleで検索すると、かなり長いアイデアのリストが作成されました。あなたの答えはlog2（x）/ 2であり、4の正確なべき乗の答えしか求められない場合は、結果が整数であることを確認する方法を見つける必要があります。

プログラミングしている場合x86プロセッサの場合、BitScanForward & BitScanReverseを使用して設定ビットを検索し、それを使用してlog2を計算することができます。次のコードはVisual Studioで動作します.GCCなどでは、インラインアセンブリを行う他の方法があります。

uint32_t exact_power_of_4_scan(uint32_t num) 
{ 
    unsigned long reverse; 
    unsigned long forward; 

    if (!_BitScanReverse(&reverse, num)) return 0; 
    _BitScanForward(&forward, num); 

    if (reverse != forward) return 0; // makes sure only a single bit is set 
    if (reverse & 0x1) return 0; // only want every other power of 2 
    return reverse/2; 
} 

ポータブルなソリューションが必要な場合は、テーブルルックアップが役立つかもしれませんが、より複雑です。

uint8_t not_single_bit[256] = { 
    1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
}; 

uint8_t log2_table[256] = { 
    0, 0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 
    4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 
}; 

uint32_t exact_power_of_2(uint32_t num) 
{ 
    auto a = not_single_bit[num & 0xff]; 
    auto b = not_single_bit[(num >> 8) & 0xff]; 
    auto c = not_single_bit[(num >> 16) & 0xff]; 
    auto d = not_single_bit[(num >> 24) & 0xff]; 

    if (a + b + c + d != 3) { 
    return 0; 
    } 

    if (!a) { 
    return log2_table[num & 0xff]; 
    } 
    if (!b) { 
    return log2_table[(num >> 8) & 0xff] + 8; 
    } 
    if (!c) { 
    return log2_table[(num >> 16) & 0xff] + 16; 
    } 

    return log2_table[(num >> 24) & 0xff] + 24; 
} 

uint32_t exact_power_of_4(uint32_t num) 
{ 
    auto ret = exact_power_of_2(num); 

    if (ret & 0x1) return 0; 
    return ret/2; 
} 

どちらも線形アルゴリズムです。最初のものはおそらくnumのほぼすべての値のためにループを打ち消すでしょうが、私はそれをテストしていません。 2番目のものは、おそらく大規模な場合にのみ有効ですnum s。

Answer 2

数学は結果があるまで4で割っておくことであろうもはや4で割り切れません。

実際にビット単位の操作で行う場合は、テクニックhereを使用して、末尾のゼロビットの数（つまり、値が2で割り切れる回数）を数えます。それらは、後続ビットの対をカウントするように調整することができる（すなわち、2ではなく4の累乗による除算）。

未定義または指定されていない動作が発生しないように、値をunsignedに設定する必要があります。

ビット単位の操作がより効率的な解決策になるというあなたの主張に異議を申し立てます。特に現代のコンパイラでは、テストなしで与えられたものではありません。