```
int common_prefix_length(int a, int b)
{
return __builtin_clz(a ^ b);
}
```

What's this doing? Let's break it down:

**is the bitwise-xor of a and b. The boolean xor operation is true when one of it's inputs is true and the other is false; or false if both have the same value. Another way to put this is that xor returns true when its inputs are different and false if they're the same. The bitwise-xor operation then, returns a value which has zeros for every bit that is the same in both a and b; and ones for every bit that's different.**

`a ^ b`

**is a GCC intrisinc function which counts the number of leading zero bits of its argument. It compiles down to a single machine code instruction on hardware that supports it (which includes every Intel chip made in this decade). The Visual C++ equivalent is the**

`__builtin_clz`

**intrinsic, which has a slightly more complicated API; implementing the above with it is left as an exercise for the reader. :-)**

`_BitScanReverse`

Passing the result of

**to**

`a ^ b`

**means we're counting the leading zero bits in a number where a zero bit indicates that the corresponding bits in a and b had the same value; which is exactly how we get the length of the common prefix.**

`__builtin_clz`

You can get the common suffix in the same way. The only difference is that you use the

**intrinsic (Visual C++:**

`__builtin_ctz`

**) instead, to count the**

`_BitScanForward`

*trailing*zero bits:

```
int common_suffix_length(int a, int b)
{
return __builtin_ctz(a ^ b);
}
```

Neat huh?

## No comments:

## Post a Comment