fIn programming, an n-bit integer is internally stored as a binary number that consists of n bits. For example, the C++ type int is a 32-bit type, which means that every int number consists of 32 bits. For example, the bit representation of the int number 43 is

$$00000000000000000000000000101011$$

To convert a bit representation $b_k\ldots b_2b_1b_0$ into a number, the formula is given by

$$b_k 2^k + \cdots + b_22^2+b_12^1+b_02^0.$$

Connections

• A signed number $-x$ equals an unsigned number $2^n-x$.

Bit Operations

1. The and operation x & y produces a number that has one bits in positions where both x and y have one bits.
   1. If a number $x$ is even, then x & 1 = 0.
   2. If a number $x$ is odd, then x & 1 = 1.
   3. A number $x$ is divisible by $2^k$ exactly when x & (2^k-1) = 0.
2. The or operation x | y produces a number that has one bits in positions where at least one of $x$ and $y$ have one bits.
3. The xor operation x^y produces a number that has one bits in positions where exactly one of x and y have one bits
4. The not operation ~x produces a number where all the bits of $x$ have been inverted.
   1. $~x = -x - 1$
5. The left bit shift x << k appends $k$ zero bits to the number and the right bit shift x >> k removes the $k$ last bits from the number.
   1. Note that $x << k \Leftrightarrow x\cdot 2^k$ and $x >> k \Leftrightarrow \text{floor}(x/2^k)$
   2. $14 << 2 = 56 \Leftrightarrow 1110, 111000$
   3. $49 >> 3 = 6$ because $49 \Leftrightarrow 110001$ and $6 \Leftrightarrow 1110$.
6. A bit mask of the form 1 << k has one bit in position $k$, and all other bits are zero. As a remark, the kth bit of a number is one exactly when x & (1 << k) is not zero.
   1. x | (1 << k) sets the $k$th bit of $x$ to one
   2. x & ~(1 << k) sets the $k$th bit of $x$ to zero.
   3. x ^ (1 << k) inverts the $k$th bit of $x$.
   4. x & (x - 1) sets the last one bit of $x$ to zero.
   5. x | (x-1) inverts all the bits after the last one bit.
   6. A positive number $x$ is a power of two exactly when x & (x - 1) = 0.

Additional Functions

1. __builtin_clz(x): the number of zeros at the beginning of the bit representation
2. __builtin_ctz(x): the number of zeros at the end of the bit representation
3. __builtin_popcount(x): the number of ones in the bit representation
4. __builtin_parity(x): the parity (even or odd) of the number of ones in the bit representation

Set Operations as Bit Operations

_int x = (1<<1)|(1<<3)|(1<<4)|(1<<8);_
_int y = (1<<3)|(1<<6)|(1<<8)|(1<<9);_
_int z = x|y;_
_cout << __builtin_popcount(z) << "\n"; // 6_