<style> .reveal-up, .reveal-left, .reveal-right, .reveal-stagger > * { opacity: 1 !important; transform: none !important; } </style>
  1. Learn
  2. DSA
  3. Hashing and problem-solving techniques
All lessons in this course

Foundations

Linear data structures

Searching and sorting

Hashing and problem-solving techniques

Trees

Graphs

Algorithm design

Master level

Lesson 24 of 50 14 minIntermediate

Bit manipulation

Work directly with the bits of an integer: the bitwise operators, setting and testing single bits, classic tricks such as powers of two and XOR, and using bits to represent sets.

An int is 32 bits, each 0 or 1. Every bit is a power of two: the number is the sum of the powers whose bit is 1. 13 is 8 + 4 + 1, so its bits are 1101. Bit manipulation means using operators that work on all bits at once. It is fast (one CPU instruction) and compact (32 yes/no flags in one int).

Binary.cs
int x = 0b1101;                                   // binary literal: 13Console.WriteLine(x);Console.WriteLine(Convert.ToString(x, 2));         // back to binary textConsole.WriteLine(Convert.ToString(200, 2).PadLeft(8, '0'));int mask = 0b_1111_0000;                          // _ separates digits for readingConsole.WriteLine(mask);
Output
13
1101
11001000
240

The bitwise operators

OperatorNameEach result bit is 1 when…12 op 10 (1100, 1010)
a & bANDboth bits are 11000 = 8
a | bORat least one bit is 11110 = 14
a ^ bXORthe bits differ0110 = 6
~aNOTthe bit was 0−13 (all 32 bits flipped)
a << nleft shiftbits move n places left (× 2ⁿ)12 << 2 = 48
a >> nright shiftbits move n places right (÷ 2ⁿ, rounding down)12 >> 1 = 6
Interactive

Bit lab

Click any bit to flip it. Each column is a power of two; a number is the sum of the columns that are 1.

1286432168421dechexA120x0CB100x0A=0000100080x08
a & b → 8. 1 only where both are 1. Use it to test or keep bits (a mask).
A has 2 one-bits (BitOperations.PopCount) · power of two: no · even: yes (a & 1) == 0
Operators.cs
int a = 0b1100, b = 0b1010;Console.WriteLine(Convert.ToString(a & b, 2));Console.WriteLine(Convert.ToString(a | b, 2));Console.WriteLine(Convert.ToString(a ^ b, 2));    // leading zero is not printedConsole.WriteLine(a << 2);Console.WriteLine(a >> 1);Console.WriteLine(~a);
Output
1000
1110
110
48
6
-13

Why is ~12 equal to −13? Negative numbers are stored in two’s complement: −x is ~x + 1. So ~x is always −x − 1. The top bit is the sign bit.

Setting, clearing, toggling and testing one bit

1 << k is a number with only bit k set: a mask. Combine it with the operators to work on one bit without touching the others:

SingleBits.cs
int flags = 0;flags |= 1 << 3;                        // set bit 3flags |= 1 << 0;                        // set bit 0Console.WriteLine(Convert.ToString(flags, 2).PadLeft(8, '0')); bool has3 = (flags & (1 << 3)) != 0;    // test bit 3flags &= ~(1 << 0);                     // clear bit 0flags ^= 1 << 5;                        // toggle bit 5Console.WriteLine(has3);Console.WriteLine(Convert.ToString(flags, 2).PadLeft(8, '0'));
Output
00001001
True
00101000

This is exactly what a C# [Flags] enum does behind the scenes (see the enums lesson in the C# course): each named value is one bit, | combines them and HasFlag tests with &.

Classic tricks

  • (x & 1) == 0: x is even (the lowest bit is the 1s place).
  • x & (x − 1): removes the lowest 1 bit. Subtracting 1 flips the lowest 1 to 0 and the zeros below it to 1, so AND clears them all.
  • x > 0 && (x & (x − 1)) == 0: x is a power of two (exactly one 1 bit).
  • x & −x: keeps only the lowest 1 bit. Fenwick trees (Master module) are built on this.
  • x ^ x == 0 and x ^ 0 == x: XOR cancels pairs.
Tricks.cs
using System.Numerics; static bool IsPowerOfTwo(int x) => x > 0 && (x & (x - 1)) == 0; Console.WriteLine(IsPowerOfTwo(64));Console.WriteLine(IsPowerOfTwo(96));Console.WriteLine(BitOperations.PopCount(0b1011_0110u));   // number of 1 bitsConsole.WriteLine(BitOperations.Log2(1000u));              // highest set bitConsole.WriteLine(int.IsPow2(1024));                       // built in since .NET 7
Output
True
False
5
9
True

Because XOR cancels pairs, XOR-ing a list where every value appears twice except one leaves exactly that one value, in O(n) time and O(1) memory:

SingleNumber.cs
int[] tags = { 4, 7, 2, 7, 4 };int single = 0;foreach (int t in tags) single ^= t;    // pairs cancel outConsole.WriteLine(single);
Output
2

Bits as a set: every combination

With n items, an n-bit number can say “in” or “out” for each one. Counting from 0 to 2ⁿ − 1 visits every subset exactly once. Here are all combinations of three load cases:

Subsets.cs
string[] loads = { "dead", "live", "wind" }; for (int mask = 0; mask < 1 << loads.Length; mask++){    var picked = new List<string>();    for (int i = 0; i < loads.Length; i++)        if ((mask & (1 << i)) != 0) picked.Add(loads[i]);   // bit i set: item i is in     string bits = Convert.ToString(mask, 2).PadLeft(loads.Length, '0');    Console.WriteLine($"{bits}: {(picked.Count == 0 ? "none" : string.Join(" + ", picked))}");}
Output
000: none
001: dead
010: live
011: dead + live
100: wind
101: dead + wind
110: live + wind
111: dead + live + wind

There are 2ⁿ subsets, so this is only practical for small n (up to about 20–25). The same “set as bits” idea powers some dynamic programming solutions later in the course.

Shifting negative numbers

>> on an int copies the sign bit in from the left, so negative numbers stay negative (it divides by 2ⁿ, rounding down). C# 11 added >>>, which always shifts in zeros:

Shifts.cs
int n = -16;Console.WriteLine(n >> 2);     // sign kept: -4Console.WriteLine(n >>> 28);   // zeros shifted in: the top 4 bits, 1111
Output
-4
15
Quick check

What is 12 & (12 − 1)?

Quick check

Which expression sets bit 4 of x and leaves the other bits alone?

Practice

Write Hamming(int a, int b): the number of bit positions where a and b differ. Hamming(1, 4) = 2 (001 vs 100), Hamming(3, 1) = 1, Hamming(255, 0) = 8. Count the bits yourself with the x & (x − 1) trick instead of PopCount.

Show a hint

XOR gives a 1 exactly where the bits differ. Then count the 1 bits: each x &= x − 1 removes one, so loop until x is 0.

Show the solution
Solution.cs
static int Hamming(int a, int b){    int x = a ^ b, count = 0;   // 1 where the bits differ    while (x != 0)    {        x &= x - 1;             // remove the lowest 1 bit        count++;    }    return count;} Console.WriteLine(Hamming(1, 4));Console.WriteLine(Hamming(3, 1));Console.WriteLine(Hamming(255, 0));
Output
2
1
8

Remember

  • & keeps or tests bits, | sets them, ^ flips them, ~ inverts all, << / >> shift (× / ÷ by powers of two).
  • 1 << k is a mask for bit k; always bracket bitwise expressions before comparing.
  • x & (x − 1) clears the lowest 1 bit; a power of two has exactly one 1 bit; XOR cancels pairs.
  • An n-bit mask can represent a subset of n items; counting 0 … 2ⁿ − 1 visits every subset.
0 of 50 lessons completed