快速方式，如果一個整數是2^n倍另一個整數

Question

給定兩個嚴格的正整數X和ÿ在基座2表示，是否有一個快速的方法，以檢查是否X = 2^NY其中n是一個整數？ （這是相同的檢查，如果X是Ÿ移位版本，但我不知道這是其實更容易。）

一種解決方案是檢查X％Y = 0和x/y是兩個冪（這可以非常有效地完成[1]），但這需要模和分區，兩個昂貴的操作，即使在現代架構上也是如此。

[1] X是二的冪當且僅當（X &（X - 1））= 0

Answer 1

模數和除法可能被合併到相同的操作，但它仍然會很慢。

正如你所提到的，另一種方法是嘗試一些n's。哪個n的？你可以做一個二進制搜索。這當然也很慢。無論比第一種方法更快還是更慢，誰知道。取決於一個處理器的分割速度有多快，這在每個處理器上都不一樣。

如果你有一個numberOfTrailingZeros原語（又名tzcnt或幾乎等同ffs或_BitscanForward），您可以正常化x和y這樣的：

int nx = x >> tzcnt(x); 
int ny = y >> tzcnt(y); 

那麼如果nx == ny，x是電源的兩倍數爲y，但它可能是兩個負值，因此您還必須檢查tzcnt(x) >= tzcnt(y)。

編輯：我想檢查一下x >= y是否足以解決這個問題。

Answer 2

如果你要抱怨劃分和模數運算的過度努力，那麼只需重複移位和比較位模式。這是最簡單的。但是，假設採用64位整數，並且假設分佈均勻（可能無效），則需要平均32次移位並比較迭代才能執行此測試。無論是移位和比較32次都快於一個整數除法，還有幾次減法和AND是令人懷疑的。如果您不確定，請查看處理器手冊。