Inside a computer, every number is stored as a sequence of bits: zeros and ones.
13 → 1101Most of the time we never think about these bits. But sometimes working with them directly lets us write solutions that are faster, use less memory, and are surprisingly elegant. For example:
Checking if a number is odd with a single operation.
Checking if a number is a power of two in
O(1).Finding the one number that appears once while every other number appears twice, using no extra memory.
Generating all subsets of a set without recursion.
Working directly with the bits of a number is called Bit Manipulation. It is a favourite topic in interviews at product-based companies.
Binary Numbers: A Quick Refresher
In the decimal system, each position is a power of 10. In binary, each position is a power of 2.
Bit position: 3 2 1 0
Power of 2: 8 4 2 1
Bits of 13: 1 1 0 1
13 = 8 + 4 + 0 + 1Bits are numbered from the right, starting at position 0. Position 0 is called the least significant bit (LSB).
In Java, an int has 32 bits and a long has 64 bits. You can see the binary form of a number with Integer.toBinaryString(), which leaves out the leading zeros.
You can also write binary literals directly in Java using the 0b prefix:
int n = 0b1101; // 13Bitwise Operators in Java
Operator | Name | Rule (for each bit) |
|---|---|---|
| AND | 1 only if both bits are 1 |
| OR | 1 if at least one bit is 1 |
| XOR | 1 if the bits are different |
| NOT | Flips every bit |
| Left shift | Moves bits left, fills with 0 |
| Signed right shift | Moves bits right, fills with the sign bit |
| Unsigned right shift | Moves bits right, fills with 0 |
Let's apply them to a = 12 (1100) and b = 10 (1010):
1100 (12) 1100 (12) 1100 (12)
& 1010 (10) | 1010 (10) ^ 1010 (10)
------ ------ ------
1000 (8) 1110 (14) 0110 (6)class Main {
public static void main(String[] args) {
int a = 12; // 1100
int b = 10; // 1010
System.out.println("a & b = " + (a & b));
System.out.println("a | b = " + (a | b));
System.out.println("a ^ b = " + (a ^ b));
System.out.println("~a = " + (~a));
System.out.println("a << 1 = " + (a << 1));
System.out.println("a >> 2 = " + (a >> 2));
System.out.println(Integer.toBinaryString(a & b));
System.out.println(Integer.toBinaryString(a | b));
System.out.println(Integer.toBinaryString(a ^ b));
}
}Output:
a & b = 8
a | b = 14
a ^ b = 6
~a = -13
a << 1 = 24
a >> 2 = 3
1000
1110
110Why is ~12 equal to -13? To understand that, we need to see how Java stores negative numbers.
Negative Numbers and Two's Complement
Java stores int values in two's complement form. The leftmost bit (bit 31) is the sign bit: 0 for non-negative numbers and 1 for negative numbers.
To get -x from x in two's complement: flip all the bits, then add 1.
5 = 00000000 00000000 00000000 00000101
~5 = 11111111 11111111 11111111 11111010 (this is -6)
-5 = 11111111 11111111 11111111 11111011 (~5 + 1)This gives two very useful identities:
~x = -x - 1
-x = ~x + 1So ~12 = -13 and ~5 = -6.
An int can hold values from -231 to 231 - 1, that is, from -2,147,483,648 to 2,147,483,647.
class Main {
public static void main(String[] args) {
System.out.println(Integer.toBinaryString(5));
System.out.println(Integer.toBinaryString(-5));
System.out.println(-16 >> 2);
System.out.println(-16 >>> 28);
System.out.println(-1 >>> 1);
System.out.println(~5);
System.out.println(Integer.MAX_VALUE);
System.out.println(Integer.MAX_VALUE + 1);
}
}Output:
101
11111111111111111111111111111011
-4
15
2147483647
-6
2147483647
-2147483648Notice the last line: adding 1 to the largest int wraps around to the smallest int. This is called overflow.
>> vs >>>
>>keeps the sign.-16 >> 2is-4.>>>fills with zeros, so a negative number becomes a (usually large) positive number.-1 >>> 1is2147483647.
For non-negative numbers, both give the same result.
Shifts as Multiplication and Division
Shifting left by one position doubles a number, just like adding a zero to the end of a decimal number multiplies it by 10:
x << k = x × 2ᵏ (as long as it does not overflow)
x >> k = x ÷ 2ᵏ (rounded down, towards negative infinity)13 << 2 = 1101 → 110100 = 52
13 >> 1 = 1101 → 110 = 6Modern compilers already turn x * 2 into a shift when it helps, so in real code you should write whatever is clearer. In DSA, though, you will often see 1 << k used to mean 2k.
Working with Individual Bits
Almost every bit trick is built from one simple tool: a mask with a single 1 at position i.
1 << i
1 << 0 = 0001
1 << 1 = 0010
1 << 2 = 0100
1 << 3 = 1000With this mask we can do four basic operations:
Operation | Expression | Why it works |
|---|---|---|
Check bit |
| AND keeps only bit |
Set bit |
| OR with 1 always gives 1 |
Clear bit |
| The mask has 0 only at |
Toggle bit |
| XOR with 1 flips the bit |
Let's try them on n = 13 (1101):
Check bit 2: 1101 & 0100 = 0100 ≠ 0 → set
Check bit 1: 1101 & 0010 = 0000 → not set
Set bit 1: 1101 | 0010 = 1111 (15)
Clear bit 2: 1101 & 1011 = 1001 (9)
Toggle bit 0: 1101 ^ 0001 = 1100 (12)class Main {
static boolean isBitSet(int n, int i) {
return (n & (1 << i)) != 0;
}
static int setBit(int n, int i) {
return n | (1 << i);
}
static int clearBit(int n, int i) {
return n & ~(1 << i);
}
static int toggleBit(int n, int i) {
return n ^ (1 << i);
}
public static void main(String[] args) {
int n = 13; // 1101
System.out.println("Is bit 2 set? " + isBitSet(n, 2));
System.out.println("Is bit 1 set? " + isBitSet(n, 1));
System.out.println("Set bit 1: " + setBit(n, 1));
System.out.println("Clear bit 2: " + clearBit(n, 2));
System.out.println("Toggle bit 0: " + toggleBit(n, 0));
System.out.println("13 is odd? " + ((n & 1) == 1));
System.out.println("13 * 4 = " + (n << 2));
System.out.println("13 / 2 = " + (n >> 1));
}
}Output:
Is bit 2 set? true
Is bit 1 set? false
Set bit 1: 15
Clear bit 2: 9
Toggle bit 0: 12
13 is odd? true
13 * 4 = 52
13 / 2 = 6Odd or Even
A number is odd exactly when its last bit (bit 0) is 1. So (n & 1) == 1 means odd. This also works for negative numbers in Java, because -3 in two's complement still ends with a 1.
(Be careful with n % 2 == 1: for negative odd numbers, n % 2 is -1 in Java, so that check fails. n % 2 != 0 is safe.)
Classic Bit Tricks
1. Check if a Number Is a Power of Two
A power of two has exactly one set bit:
1 = 0001
2 = 0010
4 = 0100
8 = 1000Subtracting 1 turns that single 1 into 0 and all the bits to its right into 1:
8 = 1000
8 - 1 = 0111
8 & 7 = 0000 → power of two
6 = 0110
6 - 1 = 0101
6 & 5 = 0100 → not a power of twoSo n & (n - 1) is 0 exactly when n has at most one set bit. We must also check n > 0, because 0 & -1 is also 0, and negative numbers are never powers of two.
class Main {
static boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
public static void main(String[] args) {
int[] tests = {0, 1, 2, 6, 8, 64, 100, -8};
for (int t : tests) {
System.out.println(t + " -> " + isPowerOfTwo(t));
}
}
}Output:
0 -> false
1 -> true
2 -> true
6 -> false
8 -> true
64 -> true
100 -> false
-8 -> false2. Count the Set Bits
The number of 1 bits in a number is also called its population count or Hamming weight.
The simple way checks every bit, which takes up to 32 steps for an int.
A smarter way is Brian Kernighan's algorithm. The expression n & (n - 1) removes the lowest set bit of n. So we repeat it until n becomes 0, and count how many times we did it:
n = 29 = 11101
11101 & 11100 = 11100 (count 1)
11100 & 11011 = 11000 (count 2)
11000 & 10111 = 10000 (count 3)
10000 & 01111 = 00000 (count 4)The loop runs only as many times as there are set bits. Java also has the built-in Integer.bitCount().
class Main {
// Simple way: check every bit
static int countBitsSimple(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>>= 1; // unsigned shift, works for negatives too
}
return count;
}
// Brian Kernighan's algorithm: removes the lowest set bit each time
static int countBitsKernighan(int n) {
int count = 0;
while (n != 0) {
n = n & (n - 1);
count++;
}
return count;
}
public static void main(String[] args) {
int n = 29; // 11101
System.out.println(countBitsSimple(n));
System.out.println(countBitsKernighan(n));
System.out.println(Integer.bitCount(n));
System.out.println(countBitsKernighan(-1));
System.out.println("Lowest set bit of 12: " + (12 & -12));
}
}Output:
4
4
4
32
Lowest set bit of 12: 4Notice that the simple version uses >>>=. If we used >>= on a negative number, the sign bit would keep filling in 1s and the loop would never end.
The last line shows another famous trick: n & -n isolates the lowest set bit. For 12 (1100), the lowest set bit is 0100, which is 4.
3. XOR Tricks
XOR has three properties that make it extremely useful:
x ^ 0 = x (XOR with 0 changes nothing)
x ^ x = 0 (a number cancels itself)
a ^ b = b ^ a (order does not matter, and grouping does not matter either)Single Number: Every element appears twice except one. Find it.
If we XOR all the numbers together, every pair cancels to 0, and only the single number remains:
4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4Missing Number: An array contains n distinct numbers from the range 0 to n. Find the one that is missing. XOR all indexes 0..n with all the array values: every number that is present cancels out, and the missing one is left.
Swap without a temporary variable: Three XOR operations swap two variables.
class Main {
static int singleNumber(int[] nums) {
int result = 0;
for (int x : nums) {
result ^= x;
}
return result;
}
static int missingNumber(int[] nums) {
int n = nums.length;
int result = 0;
for (int i = 0; i <= n; i++) {
result ^= i;
}
for (int x : nums) {
result ^= x;
}
return result;
}
public static void main(String[] args) {
System.out.println(singleNumber(new int[] {4, 1, 2, 1, 2}));
System.out.println(missingNumber(new int[] {3, 0, 1}));
int a = 5, b = 9;
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("a = " + a + ", b = " + b);
}
}Output:
4
2
a = 9, b = 5Both singleNumber and missingNumber run in O(n) time and O(1) space. A HashSet-based solution would need O(n) extra space.
The XOR swap is a fun interview trick, but don't use it in real code. A normal swap with a temporary variable is clearer, and the XOR swap breaks if both operands refer to the same memory location (for example, swapping arr[i] with arr[j] when i == j), because x ^ x sets the value to 0.
Generating All Subsets with Bitmasks
In the Backtracking chapter you generated all subsets using recursion. Bits give us another way.
A set with n elements has 2n subsets. Each subset can be described by an n-bit number called a bitmask: bit i is 1 if element i is in the subset.
items = [a, b, c]
mask bits subset
0 000 []
5 101 [a, c] (bit 0 → a, bit 2 → c)
7 111 [a, b, c]So we simply count from 0 to 2n - 1 and decode each number:
import java.util.ArrayList;
import java.util.List;
class Main {
public static void main(String[] args) {
char[] items = {'a', 'b', 'c'};
int n = items.length;
for (int mask = 0; mask < (1 << n); mask++) {
List<Character> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
subset.add(items[i]);
}
}
String bits = String.format("%3s", Integer.toBinaryString(mask)).replace(' ', '0');
System.out.println(bits + " -> " + subset);
}
}
}Output:
000 -> []
001 -> [a]
010 -> [b]
011 -> [a, b]
100 -> [c]
101 -> [a, c]
110 -> [b, c]
111 -> [a, b, c]The bits are printed with the highest bit on the left, so bit 0 (element a) is the rightmost digit.
This takes O(2n × n) time, the same as the recursive approach. With an int mask, it works for up to about 30 elements, but 230 subsets is already over a billion, so in practice it is used for small n (around 20 or less).
Common Mistakes
1. Operator Precedence
In Java, == has higher precedence than &, ^ and |. So this line:
if (x & 1 == 0)is read as x & (1 == 0), which does not even compile in Java ("bad operand types for binary operator '&'"). In C and C++ it compiles and silently gives the wrong answer. Always use brackets:
if ((x & 1) == 0)2. Shifting Into the Sign Bit and Beyond
class Main {
public static void main(String[] args) {
System.out.println(1 << 30); // fine
System.out.println(1 << 31); // sign bit: negative!
System.out.println(1 << 32); // shift is taken modulo 32
System.out.println(1L << 32); // use long for big shifts
System.out.println(-7 >> 1); // rounds towards negative infinity
System.out.println(-7 / 2); // rounds towards zero
}
}Output:
1073741824
-2147483648
1
4294967296
-4
-31 << 31sets the sign bit, so the result is negative.For an
int, Java uses only the lowest 5 bits of the shift amount, so1 << 32is the same as1 << 0, which is1. For along, the lowest 6 bits are used.Use
1L << kwhenkcan be 31 or more.
3. >> Is Not Exactly Division for Negatives
As the last two lines above show, -7 >> 1 is -4 (rounds down) while -7 / 2 is -3 (rounds towards zero).
4. Using >> in Loops on Negative Numbers
A loop like while (n != 0) { n >>= 1; } never ends for a negative n, because the sign bit keeps filling in 1s and n gets stuck at -1. Use >>> instead.
5. Confusing Logical and Bitwise Operators
&& and || work on boolean values and short-circuit. & and | work bit by bit on integers (and on booleans without short-circuiting).
Quick Reference
Task | Expression |
|---|---|
Is |
|
Check bit |
|
Set bit |
|
Clear bit |
|
Toggle bit |
|
Remove the lowest set bit |
|
Isolate the lowest set bit |
|
Is |
|
Multiply by 2k |
|
Divide by 2k (non-negative |
|
Count set bits |
|
Number of subsets of |
|
Where Is Bit Manipulation Used?
Flags and permissions: storing many true/false options in one integer (for example, read/write/execute permissions in Linux are bits).
Bitmask DP: representing which items have been used, as in the Travelling Salesman Problem.
Networking: subnet masks use AND to find the network part of an IP address.
Hashing: Java's
HashMapuses bit operations to spread hash codes and pick buckets.Graphics, compression and cryptography: packing data and mixing bits efficiently.
Practice Problems
Number of 1 Bits
Power of Two
Single Number
Missing Number
Counting Bits
Reverse Bits
Hamming Distance
Subsets (solve it with bitmasks)
Single Number III (two numbers appear once)
Sum of Two Integers (add without using
+)
The Main Idea
Bit manipulation means working directly with the binary digits of a number using the operators:
& AND | OR ^ XOR ~ NOT
<< left shift >> signed right shift >>> unsigned right shiftThe most important tricks to remember are:
1 << i → mask for bit i
n & (n - 1) → removes the lowest set bit
n & -n → isolates the lowest set bit
x ^ x = 0 → pairs cancel outBit manipulation lets us solve certain problems in O(1) time or O(1) space by treating a number as a row of switches that we can check, set, clear and flip directly.