These are some binary tricks that I collected on the web. Useful or not. Some of them are the reinventing-the-wheel product of mine. But it is nice to keep a record here.

## Return right-most bit

Return right-most bit set, either one:

```
x & -x
x & (~x + 1)
```

Return right-most bit unset:

```
~x & (x + 1)
```

By the similar logic, the increment and decrement can be done bitwise:

```
x = -(~x); // x++
x = ~(-x); // x--
```

And also doing negation:

```
x = (~x)+1; // x = -x
x = (x ^ -1)+1; // x = -x
```

So we also have the following two ways to do absolute value (assume integer of 32-bit):

```
(x ^ (x>>31)) - (x>>31) // (x>0)?x:-x
(x ^ (x>>31)) + (unsigned(x)>>31)
```

## Comparing integers of equal sign

```
if ((a ^ b) >= 0) // Same as a*b > 0
```

But note, when any of the two integer is zero, the construct is not exactly equal: In this case, zero is treated as positive.

## Even/Odd check

```
if ((a & 1) == 0) // Same as a%2 == 0
```

## Reset the right-most bit

Right-most set-bit become unset

```
x & (x - 1)
```

We can check if a positive number is a power of 2 by verifying `x & (x-1) == 0`

. Alternative ways to check is `x & -x == x`

.

## Get the next power of 2

Simply speaking, find the MSB set, and left shift by 1. The key idea below is to set all bits after the MSB set, then increment it.

```
x |= x>>1;
x |= x>>2;
x |= x>>4;
x |= x>>8;
x |= x>>16;
x++;
```

But the above code will convert a power of 2 to the next power of 2 rather than
staying there. Thus it is not “rounding” to next power of 2 exactly. To do
rounding, i.e. not modifying the value if it is already a power of 2, do a `x--`

first.

## Tell the position of the right-most set bit

```
popcount(x ^ (x-1))
```

## Reverse bits

```
x = ((x>>1) & 0x55555555) | ((x<<1) & 0xAAAAAAAA);
x = ((x>>2) & 0x33333333) | ((x<<2) & 0xCCCCCCCC);
x = ((x>>4) & 0x0F0F0F0F) | ((x<<4) & 0xF0F0F0F0);
x = ((x>>8) & 0x00FF00FF) | ((x<<8) & 0xFF00FF00);
x = ((x>>16)& 0x0000FFFF) | ((x<<16)& 0xFFFF0000);
```

# Rounding

If we want to round a number `x`

to the *lower* multiple of `y`

(i.e. round down), we can do this:

```
int x;
x = (int)(x/y)*y;
```

To round to the *upper* multiple of `y`

(i.e. round up), it is:

```
x = (int)((x+y-1)/y)*y;
```

To round off, i.e. to the nearest multiple of `y`

, it is:

```
x = (int)((x+y/2)/y)*y;
```

## Guarantee a positive/negative value

For an integer `x`

, make it zero if it is positive/negative and leave it
untouched otherwise. To make sure it is non-positive, mask it with 0 if its MSB
is 0:

```
x &= x >> 31;
```

To make sure it is non-negative, mask it with 0 if its MSB is 1:

```
x &= (~x) >> 31;
```

## Identities

```
x + y == (x & y) + (x | y)
x | y == (x ^ y) + (x & y)
```

More: