# Bit manipulation cheatsheet

March 31, 2021

## Get a bit

$\begin{array}{ccc} &0001&0111 \\ \And & 0000 & 000\textcolor{#EC407A}{1} \\ \hline & 0000 & 0001 \end{array}$

### Get last bit

n & 1

### Check if n is even

n & 1 == 0

### Get bit at position k

(n >> k) & 1

## Set / clear a bit at position k

### Set a bit

$\begin{array}{ccc} & 0001 & 0111 \\ \mathbin{|} & 0000 & \textcolor{#EC407A}{1}000 \\ \hline & 0001 & 1111 \end{array}$
n |= 1 << k

### Clear a bit

$\begin{array}{ccc} & 0001 & 0111 \\ \And & 1111 & 1\textcolor{#EC407A}{0}11 \\ \hline & 0001 & 0011 \end{array}$
n &= ~(1 << k)

### Toggle a bit

$\begin{array}{ccc} \verb!^! & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & \textcolor{#ec407a}{0} \end{array}$
💡

^ is similar to | except that $1 xor 1 = 0$.

n ^= 1 << n

Write C expressions, in terms of variable x, for the following values.

The least significant byte of x, with all other bits set to $0$.

x & 0xff

The least significant byte set to all ones, and all other bytes of x left unchanged.

x | 0xff

CS-APP practice problem 2.12

## n & (n - 1) trick

🛎️

n & n - 1 has the effect of flipping the least significant $1$ bit of n.

Check out this detailed explanation.

You can use this trick to solve following LeetCode questions.

public int hammingWeight(int n) {
int ret = 0;
for (; n != 0; n = n & (n - 1)) ret++；
return ret;
}

Notice in the decimal system, we write $10^n$ as $1$ followed by $n$ zeros.

By the same token, the binary representation of $2^n$ is $1$ followed by $n$ zeros.

// Check if the number would turn to 0
// after flipping the least significant 1 bit.
public boolean isPowerOfTwo(int n) {
if (n == 0) return false;
long N = (long) n;
return (N & (N - 1)) == 0;
}

To check if a number is a power of $4$, we first check if it’s power of $2$ by applying the $n \And (n - 1)$ trick. A power of $2$ number has only one $1$ bit. If it’s power of $4$, this $1$ bit must be followed by an even number of $0$ bits. In other words, the $1$ bit must appear at even position of the binary representation. We can use a bit mask to check if the 1 bit is at odd position. If so, it’s not power of $4$.

public boolean isPowerOfFour(int n) {
if (n == 0) return false;
long N = (long) n;
return (N & (N - 1)) == 0
&& (N & 0xaaaaaaaa) == 0;
}

Note 0xa is equivalent to 0b1010.