Bit manipulation: keeping the common part at the left of the last different bit
algorithm, bit-manipulation, c, c++, optimization
Solution
My answer is based on @JerryCoffin's one.
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);
Problem
Consider two numbers written in binary (MSB at left): ``` X = x7 x6 x5 x4 x3 x2 x1 x0 ``` and ``` Y = y7 y6 y5 y4 y3 y2 y1 y0 ``` These numbers can have an arbitrary number of bits but both are of the same type. Now consider that `x7 == y7`, `x6 == y6`, `x5 == y5`, but `x4 != y4`. How to compute: ``` Z = x7 x6 x5 0 0 0 0 0 ``` or in other words, how to compute efficiently a number that keeps the common part at the left of the last different bit ? ``` template <typename T> inline T f(const T x, const T y) { // Something here } ``` For example, for: ``` x = 10100101 y = 10110010 ``` it should return ``` z = 10100000 ``` Note: it is for supercomputing purpose and this operation will be executed hundreds of billion times so scanning the bits one by one should be avoided...