快速方式，如果一个整数是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是令人怀疑的。如果您不确定，请查看处理器手册。