Bit manipulation cheatsheet

Get a bit

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

n |= 1 << k

Clear a bit

n &= ~(1 << k)

Toggle a bit

n ^= 1 << n

Masking

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

Check out this detailed explanation.

You can use this trick to solve following LeetCode questions.

easy

№ 191. Number of 1 Bits 🐟

71% ac·力扣中文站·LeetCode

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

easy

№ 231. Power of Two

49% ac·力扣中文站

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;
}

easy

№ 342. Power of Four

50% ac·力扣中文站

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.

Reference

• 5种解法，你应该背下的位操作知识
• StackOverflow: How do you set, clear, and toggle a single bit?