# Bit Operations

- Bit Manipulation
- Extended De Morgan’s Laws
- Next Higher Number with Same Number of 1-bits
- Algorithmic & Mathematical Operations
`x >= 0 ? 1 : -1`

`x == a ? b : a`

- Average of Two Integers Without Causing Overflow
- Power of 2
- Reversing Bits
- Reference

### Bit Manipulation

`x & (x - 1)`

— turn off the rightmost 1-bit, producing 0 if none- e.g.
`01011000`

->`01010000`

**determine if an***unsigned integer*is a power of 2 or is 0

- e.g.
`x | (x + 1)`

— turn on the rightmost 0-bit, producing all 1’s if none- e.g.
`10100111`

->`10101111`

- e.g.
`x & (x + 1)`

— turn off the trailing 1’s, producing`x`

if none- e.g.
`10100111`

->`10100000`

**determine if an***unsigned integer*is of the form $2^n - 1$, 0, or all 1’s

- e.g.
`x | (x - 1)`

— turn on the trailing 0’s, producing`x`

if none- e.g.
`10101000`

->`10101111`

- e.g.
`~x & (x + 1)`

— turn off all but turning on the rightmost 0-bit only, producing 0 if none- e.g.
`10100111`

->`00001000`

- e.g.
`~x | (x - 1)`

— turn on all but turning off the rightmost 1-bit only, producing all 1’s if none- e.g.
`10101000`

->`11110111`

- e.g.
`~x & (x - 1)`

,`~(x | -x)`

, or`(x & -x) - 1`

— turn off all but turning on the trailing 0’s only, producing 0 if none- e.g.
`01011000`

->`00000111`

`~x & (x - 1)`

has some instruction-level parallelism

- e.g.
`~x | (x + 1)`

— turn on all but turning off the trailing 1’s only, producing all 1’s if none- e.g.
`10100111`

->`11111000`

- e.g.
`x & (-x)`

— turn off all but the rightmost 1-bit only, producing 0 if none- e.g.
`01011000`

->`00001000`

- e.g.
`x ^ (x - 1)`

— turn off all but turning on the trailing 0’s including the rightmost 1-bit, producing all 1’s if no 1-bit, and the integer 1 if no trailing 0’s- e.g.
`01011000`

->`00001111`

- e.g.
`x ^ (x + 1)`

— turn off all but turning on the rightmost 0-bit including the trailing 1’s, producing all 1’s if no 0-bit, and the integer 1 if no trailing 1’s- e.g.
`01010111`

->`00001111`

- e.g.
`((x | (x - 1)) + 1) & x`

or`((x & -x) + x) & x`

— turn off the rightmost contiguous 1’s- e.g.
`01011100`

->`01000000`

**determine if a***nonnegative integer*is of the form $2^j - 2^k$ for some $j \geq k \geq 0$

- e.g.

### Extended De Morgan’s Laws

Other than the original De Morgan’s Laws such as `~(x & y) = ~x | ~y`

and `~(x | y) = ~x & ~y`

, this idea can be extended further.

`~(x + y) == ~x - y`

`~(x - y) == ~x + y`

`~(x ^ y) == ~x ^ y`

`~(-x) == x - 1`

From these facts, addition can be combined with logical operations.

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

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

`x + y == x - (-y) == x - (~y + 1) == x - ~y - 1`

`x + y == (x ^ y) + ((x & y) << 1)`

- This computes the sum without carries first, and then adding carries. Note that the left shift is used since carries should be applied to the left bit of each.

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

- Let
`y0`

be a variable with 0-bit if a bit of`y`

and the corresponding bit of`x`

are the same as 1, and the same bit with`y`

otherwise. Also, let`y1 = x & y`

. Then,`y == y0 + y1`

. So,`x + y == x + (y0 + y1) == (x + y0) + y1 == (x | y) + (x & y)`

.

- Let

`x - y == x + (-y) == x + (~y + 1) == x + ~y + 1`

`x - y == (x ^ y) - ((~x & y) << 1)`

- This computes the subtraction without borrows first, and then subtracting borrows. Note that the left shift is used since borrows should be applied to the left bit of each.

`x - y == (x & ~y) - (~x & y)`

- Let $(x_i, y_i)$ be the $i$-th bit-pair of
`x`

and`y`

. Now, let`x0`

and`y0`

be variables with each $x_i$’s and $y_i$’s at the positions if $(x_i, y_i) = (1, 0)$, and with 0’s otherwise. Similarly,`x1`

and`y1`

have $x_i$’s and $y_i$’s from the pairs $(x_i, y_i) = (0, 1)$,`x2`

and`y2`

from $(x_i, y_i) = (1, 1)$, and`x3`

and`y3`

from $(x_i, y_i) = (0, 0)$. Then,`x = x0 + x1 + x2 + x3`

and`y = y0 + y1 + y2 + y3`

. So,`x - y = (x0 - y0) + (x1 - y1) + (x2 - y2) + (x3 - y3) = (x0 - y0) + (x1 - y1) = (x0 - y0) - (y1 - x1) == (x & ~y) - (~x & y)`

.

- Let $(x_i, y_i)$ be the $i$-th bit-pair of

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

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

`x & y == (~x & y) - ~x`

### Next Higher Number with Same Number of 1-bits

When bit strings are used to represent subsets, finding the next higher number with the same number of 1-bits might help to iterate through all the subsets. The idea to solve this problem is to find the rightmost contiguous group of 1’s in `x`

and the following 0’s, and *increment* that quatity to the next value that has the same number of 1’s.

```
unsigned int findNextHigherNumber(unsigned int x)
{
// e.g. x = ???0 1111 0000
unsigned int smallest = x & -x; // 0000 0001 0000
unsigned int ripple = x + smallest; // ???1 0000 0000
unsigned int ones = x ^ ripple; // 0001 1111 0000
ones = (ones >> 2) / smallest; // 0000 0000 0111
return ripple | ones; // ???1 0000 0111
}
```

### Algorithmic & Mathematical Operations

`(x - y) & -(x >= y)`

— saturation, or`std::max( x - y, 0 )`

- For signed integers, the result can be negative, which means
*overflow*in the subtraction. But,**this negative result is actually the correct difference if it is interpreted as an***unsigned integer*. - Let this operation be the function
`f(x, y)`

. Then,`f(~x, ~y) == f(y, x)`

.

- For signed integers, the result can be negative, which means
`(x ^ y) & -(x >= y) ^ y`

—`std::max( x, y )`

`(x ^ y) & -(x <= y) ^ y`

—`std::min( x, y )`

`((x - y) & -(x >= y)) + ((y - x) & -(y >= x))`

—`std::abs( x - y )`

`~((~x - y) & -(~x >= y))`

— clamp the sum of*unsigned integers*`x`

and`y`

to the maximum positive integer $2^{32} - 1$

- selective swap
- swap with a
*mask*`m`

`x = x ^ y; y = y ^ (x & m); x = x ^ y;`

- swap by chunk with a
*mask*`m`

`// swap B and D with m (the sizes of B & D must be the same) // |-- k-bit --| // x: | A | B | C | D | E | // m: | 0 | xxx | 0 | a = (x ^ (static_cast<unsigned int>(x) >> k)) & m; b = a << k; swapped = x ^ a ^ b;`

- swap with a

`x >= 0 ? 1 : -1`

`(x >> 30) | 1`

is the statement to obtain *the sign value of a 32-bit signed integer* without any branch statement. If 0 must be returned when `x == 0`

for some reason, the right workaround are as follows.

```
int signWithFourInstructions(int x)
{
// -1 (x < 0), 0 (x == 0), 1 (x > 0)
return (x >> 31) | (static_cast<unsigned int>(-x) >> 31)
}
int signWithThreeInstructions(int x)
{
// -1 (x < 0), 0 (x == 0), 1 (x > 0)
return (x > 0) - (x < 0)
}
```

In general, `signWithThreeInstructions()`

can be extended into the comparison of two integers. Note that in this case both unsigned and signed integers are supported.

```
template<typename T>
concept integer_type = std::same_as<int, T> || std::same_as<unsigned int, T>;
template<typename T>
requires integer_type<T>
T compare(T x, T y)
{
// -1 (x < y), 0 (x == y), 1 (x > y)
return (x > y) - (x < y);
}
```

`x == a ? b : a`

As a short example, for both unsigned and signed integers `a`

and `b`

, suppose `x`

should be set alternating among `a`

or `b`

. In this case, `a + b - x`

or `a ^ b ^ x`

is a far better way to do this. Overflow in calculating `a + b`

can be ignored.

### Average of Two Integers Without Causing Overflow

For two integers `x`

and `y`

, there is a well-known technique to calculate the average of them without overflow if which one is larger has been already known. `x + (y - x) / 2`

works with both unsigned and signed integers and calculates *floor averages*. What if, however, which one is larger has been unknown? It may be still fine if `min()`

and `max()`

functions are used. But, there are other techniques to do this without any branch statement. They even work with *ceiling averages* as well as floor averages.

```
template<typename T>
concept integer_type = std::same_as<int, T> || std::same_as<unsigned int, T>;
template<typename T>
requires integer_type<T>
T calculateFloorAverage(T x, T y)
{
// e.g. x = 0, y = -1 -> -1
// x = 0, y = +1 -> 0
return (x & y) + ((x ^ y) >> 1);
}
template<typename T>
requires integer_type<T>
T calculateCeilingAverage(T x, T y)
{
// e.g. x = 0, y = -1 -> 0
// x = 0, y = +1 -> 1
return (x | y) - ((x ^ y) >> 1);
}
```

Sometimes, *truncated average* is required for *signed* integers. In this case, the additional correction part is needed after the floor average. The correction is add 1 if `x + y`

is negative and odd.

```
int calculateTruncatedAverage(int x, int y)
{
// e.g. x = 0, y = +2 -> 1
// x = 0, y = +1 -> 0
// x = 0, y = -1 -> 0
// x = 0, y = -2 -> -1
int t = (x & y) + ((x ^ y) >> 1);
return t + ((static_cast<unsigned int>(t) >> 31) & (x ^ y));
}
```

### Power of 2

`x & -(1 << n)`

— the next*smaller*multiple $2^n$ for an unsigned integer`x`

, producing`x`

if`x`

is already a multiple $2^n$- The maximum of $2^n$ is the number of bits of the type of
`x`

.

- The maximum of $2^n$ is the number of bits of the type of
`x + (-x & ((1 << n) - 1))`

— the next*greater*multiple $2^n$ for an integer`x`

, producing`x`

if`x`

is already a multiple $2^n$- The maximum of $2^n$ is the number of bits of the type of
`x`

. `((1 << n) - 1)`

is a constant if`n`

is fixed.`(-x & ((1 << n) - 1))`

is useful when it is needed to know how much exactly must be added to`x`

.- If the rounding up
*in the positive direction*is valid even for negative values, this expression is correct for*signed integers*.- if
`n == 3`

and`x == -7`

, then the result is`0`

. - if
`n == 3`

and`x == -8`

, then the result is`-8`

. - if
`n == 3`

and`x == -9`

, then the result is`-8`

.

- if

- The maximum of $2^n$ is the number of bits of the type of
- Rounding
*up/down*to the next power of 2 for a*32-bit unsigned integer*`x`

- In the following code,
`__builtin_clz()`

is a built-in function to get the number of leading zeros.

- In the following code,

```
unsigned int roundDownWithCLZ(unsigned int x)
{
// must be x > 0
return 1 << (31 - __builtin_clz(x));
}
unsigned int roundUpWithCLZ(unsigned int x)
{
// must be 1 < x <= 2^(31)
return 1 << (32 - __builtin_clz(x - 1));
}
unsigned int roundDown(unsigned int x)
{
// when x == 0, return 0
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
return x - (x >> 1);
}
unsigned int roundUp(unsigned int x)
{
// when x == 0 or x > 2^(31), return 0
x--;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
return x + 1;
}
```

### Reversing Bits

Donald E. Knuth suggested the function to reverse 32 or 64 bits with a few instructions and unexpectedly irregular shifting and masking steps.

```
// 0x003f801f => 0000 0000 0011 1111 1000 0000 0001 1111
// 0x0e038421 => 0000 1110 0000 0011 1000 0100 0010 0001
// 0x22488842 => 0010 0010 0100 1000 1000 1000 0100 0010
unsigned int reverse(unsigned int x)
{
x = (x << 15) | (x >> 17);
unsigned int t = (x ^ (x >> 10)) & 0x003f801f;
x = (t | (t << 10)) ^ x;
t = (x ^ (x >> 4)) & 0x0e038421;
x = (t | (t << 4)) ^ x;
t = (x ^ (x >> 2)) & 0x22488842;
x = (t | (t << 2)) ^ x;
return x;
}
uint64_t reverse(uint64_t x)
{
x = (x << 32) | (x >> 32);
x = (x & 0x0001ffff0001ffffll) << 15 | (x & 0xfffe0000fffe0000ll) >> 17;
unsigned int t = (x ^ (x >> 10)) & 0x003f801f003f801fll;
x = (t | (t << 10)) ^ x;
t = (x ^ (x >> 4)) & 0x0e0384210e038421ll;
x = (t | (t << 4)) ^ x;
t = (x ^ (x >> 2)) & 0x2248884222488842ll;
x = (t | (t << 2)) ^ x;
return x;
}
```

## Reference

[1] Henry S. Warren. 2012. Hacker’s Delight (2nd. ed.). Addison-Wesley Professional.