（NOT繰り返し）（A＆〜（（1 << n) - 1)) > = B

Question

私は（すべての変数が正の整数である）この不等式を満たすこと1 << n最大を見つけようとしているに（1 << n）の対象を最大化：

繰り返しこれを解決

a & ~((1 << n) - 1) >= b 

は簡単です（はい、私はあなたが分割統治などを通じて、より良いパフォーマンスを得ることができます知っている）、それは私の質問はありません。

があれば、私は思ったんだけどこれは解決できる可能性があります、いくつかの種類のビットtwiddlingのような？

注1： 1回の操作で「最も近い2の累乗に丸めたり下げたりできます」と仮定します。
注2：必要に応じて、2の補数表現を仮定することができます（ただし、これは役立ちます）。

直接的な方法がある場合、これを解決するためにどのような技術を使用できますか？どういうわけか、私に教えてもらえますか？

私はaとbのようなものをたくさん試して、結果を2の次の累乗に丸めるなどしていましたが、いつもうまくいくものを見つけることはできませんでした。

Answer 1

if (a < b) { 
    oops(); 
} else if (a == b) { 
    return ctz(a); 
} else { 
    // most significant mismatching bit - must be set to 1 in a and 0 in b 
    int msmb = round_down_to_power_of_2(a^b); 
    if (b & (msmb - 1)) { 
     return ctz(msmb); 
    } else { 
     return ctz(b); 
    } 
} 

我々は4例あります

1. < Bの場合、n個の作品の無価値を。
2. a == bの場合、すべてのビットをaの最下位セットビットまでクリアすることができます。
3. a> bおよびbがaとbの間の最上位の不一致ビットよりも下のビットを設定した場合、最上位の不一致ビットまですべてのビットをクリアすることができます。
4. a> bとbがaとbの間の最上位の不一致ビットよりも下にセットビットを持たない場合、すべてのビットをbの最下位セットビットまでクリアすることができます。