位操作:将公共部分保持在最后一个不同位的左侧

Question

考虑用二进制编写的两个数字(左边是MSB):

X = x7 x6 x5 x4 x3 x2 x1 x0

和

Y = y7 y6 y5 y4 y3 y2 y1 y0

这些数字可以具有任意数量的位,但两者的类型相同.现在考虑x7 == y7,x6 == y6,x5 == y5,但x4 != y4.

如何计算:

Z = x7 x6 x5 0 0 0 0 0

或换句话说,如何有效地计算一个数字,使公共部分保持在最后一个不同位的左边？

template <typename T>
inline T f(const T x, const T y) 
{
    // Something here
}

例如,对于:

x = 10100101
y = 10110010

它应该回来

z = 10100000

注意:它用于超级计算,此操作将执行数十亿次,因此应该避免逐个扫描位...

Answer 1

我的答案基于@JerryCoffin的答案.

int d = x ^ y;
d = d | (d >> 1);
d = d | (d >> 2);
d = d | (d >> 4);
d = d | (d >> 8);
d = d | (d >> 16);
int z = x & (~d);