Yanxi Chen

Software Engineer@Amazon

2 minute read

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.

You May Also Enjoy