# Bit Hacks

### Find the minimum r of two integers x and y

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

### Modular Addition

Compute (x + y) mod n, assuming that 0 <= x < n and 0 <= y < n.

```
z = x + y;
r = z - (n & -(z >= n));
```

### Round up to a Power of 2

Compute $2^{\left \lceil{\log n}\right \rceil }$

```
// 64-bit integers
--n;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
++n;
```

Decrement and increment handles the case where n is already a power of 2.

### Least-Significant 1

Compute the mask of the least-significant 1 in word x.

```
r = x & (-x);
```

### Log Base 2 of a Power of 2

Compute log x, where x is a power of 2

```
const uint64_t deBruijn = 0x022fdd63cc95386d;
const unsigned int convert[64] =
{
0, 1, 2, 53, 3, 7, 54, 27,
4, 38, 41, 8, 34, 55, 48, 28,
62, 5, 39, 46, 44, 42, 22, 9,
24, 35, 59, 56, 49, 18, 29, 11,
63, 52, 6, 26, 37, 40, 33, 47,
61, 45, 43, 21, 23, 58, 17, 10,
51, 25, 36, 32, 60, 20, 57, 16,
50, 31, 19, 15, 30, 14, 13, 12,
};
r = convert[(x*deBruijn) >> 58];
```

Why it works?

A deBruijn sequence $s$ of length $2^k$ is a cyclic 0-1 sequence such that each of the $2^k$ 0-1 strings of length $k$ occurs exactly once as a substring of $s$.

Example k=3

```
0b00011101
0 000
1 001
2 011
3 111
4 110
5 101
6 010
7 100
convert[8] = {0, 1, 6, 2, 7, 5, 4, 3};
0b0011101 * 2^4 = 0b11010000;
0b11010000 >> 5 = 6;
convert[6] = 4;
```

### Population Count

Count the number of 1 bits in a word x

```
// Create masks
B5 = (-1) ^ ((-1) << 32);
B4 = B5 ^ (B5 << 16);
B3 = B4 ^ (B4 << 8);
B2 = B3 ^ (B3 << 4);
B1 = B2 ^ (B2 << 2);
B0 = B1 ^ (B1 << 1);
// Compute popcount
x = ((x >> 1) & B0) + (x & B0);
x = ((x >> 2) & B1) + (x & B1);
x = ((x >> 4) + x) & B2;
x = ((x >> 8) + x) & B3;
x = ((x >> 16) + x) & B4;
x = ((x >> 32) + x) & B5;
```

### Queens Problem

Place n queens on an n x n chessboard so that no queen attacks another.

Board representation:

- array of $n^2$ bytes?
- array of $n^2$ bits?
- array of $n$ bytes?
- 3 bitvectors of size $n,2n-1,2n-1$, each is enough to put in a word (unsigned int).

The n-bit vector `down`

represent whether a queen is in a given column. So placing a queen in column c is **not** safe if `down & (1 << c)`

is nonzero.

The 2n-1 bit vector `right`

represent whether a queen is in a given diagonal. So placing a queen in row r and column c is **not** safe if `right & (1 << (n - r + c))`

is nonzero.

The 2n-1 bit vector `left`

represent whether a queen is in a given reverse diagonal. So placing a queen in row r and column c is **not** safe if `left & (1 << (r + c))`

is nonzero.