← Back to C# interview home

Bit Manipulation

An integer is a row of switches. Three tricks cover most interview questions: XOR cancels pairs, x & (x - 1) turns off the lowest switch, and a mask is a set you can test in one step.

Bit questions look like puzzles, but they reward a short list of facts. Learn the operators, learn the three tricks, and learn how C# stores numbers. A C# int is exactly 32 bits in two's complement. That is good news. The bit answers you see in C or Java work as written. The traps are different ones: >> versus >>>, silent overflow, and shift counts that wrap.

When to use

• Pairs that cancel. “Every element appears twice except one.” XOR everything.
• Counting set bits. “Number of 1 bits”, “Hamming distance”, “is this a power of two”.
• Arithmetic with a hand tied. “Add without +”, “divide without /”. Build it from XOR, AND and shifts.
• Small sets as integers. “Visit every subset of up to 20 items”, or a DP whose state is “which items are used”.

Core idea

Reading the figure. Each square is one bit, highest bit on the left. Left: the red rows are a pair, and they cancel, so only the blue 3 survives. Middle: amber bits are the ones that subtracting 1 flipped. AND keeps neither, so the red bit is cleared. Right: bit i on means item i is in the set.

Two quick facts are worth having ready. x > 0 && (x & (x - 1)) == 0 means x is a power of two, because it had exactly one set bit. And x & -x isolates the lowest set bit. That is the move behind Fenwick trees. In .NET you can also call BitOperations.IsPow2(x).

Operator cheat list

• a & b: AND. 1 only where both are 1. Use it to test or clear bits.
• a | b: OR. 1 where either is 1. Use it to set bits.
• a ^ b: XOR. 1 where they differ. Use it to toggle bits or cancel pairs.
• ~a: NOT. Flips all 32 bits. On an int that equals -a - 1, so ~5 is -6. On a uint, ~5u is 4294967290.
• a << k: shift left. Bits that pass bit 31 fall off. No exception, ever.
• a >> k: shift right. On int it copies the sign bit in (arithmetic). On uint it shifts in zeros (logical).
• a >>> k: unsigned shift right (C# 11). Always shifts in zeros, even on int.
• (a >> i) & 1 reads bit i. a | (1 << i) sets it. a & ~(1 << i) clears it. a ^ (1 << i) flips it.
• Literals and printing: 0b1011_0110 and 0xFF are literals. Convert.ToString(x, 2) prints binary. Since .NET 8, x.ToString("B8") pads to 8 digits.

int vs uint, shifts, overflow, BitOperations

The Python page spends a whole section on a 0xFFFFFFFF mask. Python integers have no width, so it fakes a 32-bit register by hand. C# needs none of that. An int already is a 32-bit register. -1 is thirty-two 1 bits. Bit 31 is the sign bit. Bits shifted past the top simply fall off. So the C# work is to pick the right type and the right shift.

int or uint

• int (signed). Range -2147483648 to 2147483647. Bit 31 set means negative. Use it for values, counts and indexes.
• uint (unsigned). Range 0 to 4294967295. Same 32 bits, no sign. Use it when the question says “treat the input as an unsigned 32-bit pattern”, as Reverse Bits does.
• Moving between them. (uint)x and (int)u keep the bits and change only the meaning. (uint)(-1) is 4294967295. This cast is the whole C# version of Python's mask.
• Mixing them. int + uint becomes long. -u on a uint is also long. Cast on purpose so you know which type you hold.

>> versus >>>

• -8 >> 1 is -4. On an int, >> copies the sign bit into the top. It divides by 2 and rounds toward minus infinity.
• -8 >>> 1 is 2147483644. >>> (C# 11) shifts in a 0. Bit 31 is now clear, so the value is a big positive number.
• (uint)(-8) >> 1 is also 2147483644. On a uint, plain >> is already logical. Before C# 11 this cast was the only way.
• Which loops end. while (x != 0) x >>= 1; never ends on a negative int, because -1 >> 1 is -1. Use >>>= or a uint, and it ends in at most 32 passes.
• Shift counts wrap. For int and uint, only the low 5 bits of the count are used. So 1 << 32 is 1, not 0. For long the low 6 bits are used. Write 1L << k when k can reach 31 or more.

Overflow

• Default is unchecked. int.MaxValue + 1 at run time wraps to int.MinValue. No error. This is what bit tricks rely on.
• checked(a + b) throws. It raises OverflowException instead of wrapping. Use it when a wrap would be a bug, not a feature.
• Constants are checked at compile time. int x = int.MaxValue + 1; does not compile. Write unchecked(int.MaxValue + 1) to say you mean it.
• Abs and negate. -int.MinValue is still int.MinValue. Math.Abs(int.MinValue) throws. Widen to long first.
• Shifts never check. << drops high bits even inside checked. That makes Sum of Two Integers safe.

BitOperations

System.Numerics.BitOperations wraps single CPU instructions. Name these in an interview, then write the loop if asked. Most take uint or ulong, so cast an int first. Since .NET 7 the same calls also exist on the type itself: int.PopCount(x), int.TrailingZeroCount(x), int.Log2(x).

• PopCount(u). Number of 1 bits. PopCount(11u) is 3.
• LeadingZeroCount(u). Zeros above the highest 1. LeadingZeroCount(1u) is 31.
• TrailingZeroCount(u). Zeros below the lowest 1. This is the position of the lowest set bit.
• Log2(u). Position of the highest 1, so floor(log2 u). Log2(0) returns 0.
• RotateLeft(u, k) and IsPow2(x). A rotate moves the bits that fall off back in at the other end. IsPow2 is the one-bit test.

using System.Numerics;

/// <summary>Small demos of 32-bit behaviour. Each returns a value a test can check.</summary>
public static class IntBits
{
    /// <summary>Arithmetic shift right by one: the sign bit is copied in.</summary>
    /// <param name="x">Any int.</param>
    /// <returns>x divided by 2, rounded toward minus infinity.</returns>
    /// <example>IntBits.ArithmeticShift(-8) returns -4.</example>
    public static int ArithmeticShift(int x) => x >> 1;     // 1: shift by one place

    /// <summary>Logical shift right by one with C# 11 >>>: a 0 is shifted in.</summary>
    /// <param name="x">Any int.</param>
    /// <returns>The bits of x moved right, with bit 31 cleared.</returns>
    /// <example>IntBits.LogicalShift(-8) returns 2147483644.</example>
    public static int LogicalShift(int x) => x >>> 1;      // 1: shift by one place

    /// <summary>Reinterpret the 32 bits of an int as unsigned.</summary>
    /// <param name="x">Any int.</param>
    /// <returns>The same bit pattern read as a uint.</returns>
    /// <example>IntBits.AsUnsigned(-1) returns 4294967295.</example>
    public static uint AsUnsigned(int x) => unchecked((uint)x);

    /// <summary>Add with silent 32-bit wraparound, the default for run-time ints.</summary>
    /// <param name="a">First addend.</param>
    /// <param name="b">Second addend.</param>
    /// <returns>a + b, wrapped into the int range.</returns>
    /// <example>IntBits.WrapAdd(int.MaxValue, 1) returns -2147483648.</example>
    public static int WrapAdd(int a, int b) => unchecked(a + b);

    /// <summary>Add, but throw instead of wrapping.</summary>
    /// <param name="a">First addend.</param>
    /// <param name="b">Second addend.</param>
    /// <returns>a + b when it fits in an int.</returns>
    /// <exception cref="OverflowException">The true sum does not fit.</exception>
    /// <example>IntBits.CheckedAdd(2, 3) returns 5.</example>
    public static int CheckedAdd(int a, int b) => checked(a + b);

    /// <summary>Four BitOperations answers for one value.</summary>
    /// <param name="u">The bit pattern to inspect.</param>
    /// <returns>[PopCount, LeadingZeroCount, TrailingZeroCount, Log2].</returns>
    /// <example>IntBits.Facts(0b10110u) returns [3, 27, 1, 4].</example>
    public static int[] Facts(uint u) =>
    [
        BitOperations.PopCount(u),            // how many 1 bits
        BitOperations.LeadingZeroCount(u),    // zeros above the highest 1
        BitOperations.TrailingZeroCount(u),   // zeros below the lowest 1
        BitOperations.Log2(u),                // position of the highest 1
    ];
}

Reverse Bits is the classic question that wants uint. With an int, the first >> on a negative input would copy the sign bit and corrupt the answer. With uint, every shift brings in a 0 and the result fills all 32 bits with no sign to worry about.

/// <summary>Reverse Bits: mirror the 32 bits of an unsigned integer.</summary>
public static class ReverseBits
{
    /// <summary>Bit i of the input becomes bit 31 - i of the output.</summary>
    /// <param name="n">Any 32-bit pattern.</param>
    /// <returns>The mirrored pattern.</returns>
    /// <example>ReverseBits.Reverse(1u) returns 2147483648.</example>
    public static uint Reverse(uint n)
    {
        uint result = 0;                        // no bits placed yet

        // i counts bits moved so far. 32: a uint has exactly 32 bits.
        // Invariant: result holds the low i bits of the input, mirrored.
        for (int i = 0; i < 32; i++)
        {
            // << 1 makes room on the right. n & 1 is the lowest input bit.
            result = (result << 1) | (n & 1);
            n >>= 1;                            // uint: a 0 comes in, never a sign bit
        }
        return result;
    }
}

The templates

/// <summary>Template A: XOR every value so that pairs cancel.</summary>
public static class XorAll
{
    /// <summary>XOR of every value. Values that appear an odd number of times survive.</summary>
    /// <param name="values">Any ints, negatives included.</param>
    /// <returns>The XOR of all values, or 0 for an empty array.</returns>
    /// <example>XorAll.Of([3, 5, 3]) returns 5.</example>
    public static int Of(int[] values)
    {
        // 0 is the XOR identity: 0 ^ x == x, so starting here changes nothing.
        int acc = 0;

        // value is the next number. Invariant: acc is the XOR of all values before it.
        foreach (int value in values)
        {
            acc ^= value;                       // a second copy of value cancels the first
        }
        return acc;
    }
}

using System.Numerics;

/// <summary>Template B: visit each set bit once, lowest first.</summary>
public static class SetBits
{
    /// <summary>Positions of the 1 bits in x, lowest first. Negatives work too.</summary>
    /// <param name="x">Any int. A negative is read as its 32-bit pattern.</param>
    /// <returns>Bit positions from 0 to 31, in increasing order.</returns>
    /// <example>SetBits.Positions(0b10110) returns [1, 2, 4].</example>
    public static List<int> Positions(int x)
    {
        var positions = new List<int>();

        // Invariant: x holds the set bits not yet reported. Each pass removes one.
        // The loop stops at 0: no set bits left. A fixed 32-bit int always gets there.
        while (x != 0)
        {
            int lowest = x & -x;                // -x flips all bits above the lowest 1
            // Log2 of a one-bit number is its position. (uint): Log2 takes unsigned.
            positions.Add(BitOperations.Log2((uint)lowest));
            x &= x - 1;                         // - 1 turns the lowest 1 into 0
        }
        return positions;
    }
}

Reading the figure. Each row is one pass of the while loop. The small numbers on top are bit positions. The amber bit is the lowest 1, which x & -x isolates. Its position joins the green list. Then x &= x - 1 clears it, giving the next row.

The loop runs once per set bit, not once per bit position. On a sparse number that beats checking all 32 positions. BitOperations.TrailingZeroCount(x) gives the same position in one call. On int.MinValue, -x wraps back to int.MinValue, and the code still reports bit 31.

/// <summary>Template C: one int mask per subset.</summary>
public static class SubsetsByMask
{
    /// <summary>Every subset of items. Bit i of mask means items[i] is in.</summary>
    /// <param name="items">Up to about 20 items, since there are 2 to the n subsets.</param>
    /// <returns>All subsets, in mask order 0, 1, 2 and so on.</returns>
    /// <example>SubsetsByMask.All(["a", "b"]) returns [[], [a], [b], [a, b]].</example>
    public static List<List<string>> All(string[] items)
    {
        int n = items.Length;
        var result = new List<List<string>>();

        // 1 << n is 2 to the n: one mask per subset, from 0 (empty) to (1 << n) - 1 (all).
        // n must stay below 31, or 1 << n overflows the int.
        // Invariant: every mask below this one has already been added.
        for (int mask = 0; mask < (1 << n); mask++)
        {
            var subset = new List<string>();
            // i is the item index, 0..n-1. Invariant: subset has the chosen items before i.
            for (int i = 0; i < n; i++)
            {
                // (mask >> i) & 1 reads bit i. The 1 keeps only that bit. == 1: it is on.
                if (((mask >> i) & 1) == 1)
                {
                    subset.Add(items[i]);
                }
            }
            result.Add(subset);
        }
        return result;
    }
}

Reading the figure. Each card is one value of mask. The letters above the bits say which item each bit stands for. Green bits are on, so those items are in the subset on the right. Notice that the masks are just the numbers 0 to 7 in order, and together they cover all 8 subsets.

This is the iterative twin of backtracking subsets. It only works while 1 << n is small, so about n ≤ 20. Past 30 the int mask itself overflows. Use long and 1L << n for up to 62.

Common mistakes

• Using >> on a negative int in a loop. -1 >> 1 stays -1, so the loop never ends. Use >>> or a uint.
• Expecting 1 << 32 to be 0. C# uses only the low 5 bits of the count, so it is 1. Use 1L << k for wide masks.
• Forgetting that 1 << 31 is negative. It is int.MinValue. Comparisons like mask < (1 << 31) then go wrong. Use uint or long.
• Confusing ^ with power. 2 ^ 3 is 1, not 8. Power is 1 << k for 2 to the k, or Math.Pow for doubles.
• Trusting precedence. 1 << n - 1 is 1 << (n - 1), because - binds tighter than <<. Bracket every bit expression.
• Mixing int and uint. The result is long, and the bits you expected are gone. Cast both sides to one type.

The problems

/// <summary>Single Number: every value appears twice except one.</summary>
public static class SingleNumber
{
    /// <summary>The one value that appears once when every other appears twice.</summary>
    /// <param name="nums">Non-empty ints. Exactly one value appears once.</param>
    /// <returns>The value that appears once.</returns>
    /// <example>SingleNumber.Find([4, 1, 2, 1, 2]) returns 4.</example>
    public static int Find(int[] nums)
    {
        // Start at 0: XOR with 0 changes nothing, so 0 is the neutral start.
        int result = 0;

        // value is the next number. Invariant: result is the XOR of every number
        // seen so far. Pairs seen twice have cancelled to 0.
        foreach (int value in nums)
        {
            result ^= value;
        }
        return result;
    }
}

/// <summary>Number of 1 Bits (Hamming weight).</summary>
public static class HammingWeight
{
    /// <summary>Number of 1 bits in the 32-bit two's complement form of n.</summary>
    /// <param name="n">Any int. A negative is read as its 32-bit pattern.</param>
    /// <returns>The count of set bits, from 0 to 32.</returns>
    /// <example>HammingWeight.Count(11) returns 3. HammingWeight.Count(-1) returns 32.</example>
    public static int Count(int n)
    {
        int count = 0;                          // no set bits counted yet

        // Invariant: count + (set bits left in n) == the answer.
        // The loop stops at 0: no set bits left. For -1 it takes 32 passes:
        // -1, -2, -4, ... int.MinValue, then int.MinValue - 1 wraps and the AND gives 0.
        while (n != 0)
        {
            n &= n - 1;                         // - 1 flips the lowest 1 to 0, AND clears it
            count++;                            // one bit removed, so one more counted
        }
        return count;
    }
}

/// <summary>Counting Bits: set-bit counts for 0..n as a DP table.</summary>
public static class CountingBits
{
    /// <summary>Set-bit counts for every integer from 0 to n.</summary>
    /// <param name="n">The largest integer to count, n >= 0.</param>
    /// <returns>An array of length n + 1. Entry i is the number of 1 bits in i.</returns>
    /// <exception cref="ArgumentOutOfRangeException">n is negative.</exception>
    /// <example>CountingBits.Count(5) returns [0, 1, 1, 2, 1, 2].</example>
    public static int[] Count(int n)
    {
        ArgumentOutOfRangeException.ThrowIfNegative(n);

        // n + 1 slots so index n exists: slots 0..n. Slot 0 stays 0, the base
        // case, because 0 has no set bits. C# arrays start zeroed.
        var ones = new int[n + 1];

        // Start at 1: slot 0 is the base case. <= n so n itself is included.
        // Invariant: ones[0..i-1] are final. i >> 1 < i, so it is ready.
        for (int i = 1; i <= n; i++)
        {
            // i >> 1 drops the last bit (shift by 1 = halve). i & 1 is that
            // dropped bit: 1 if i is odd, 0 if even.
            ones[i] = ones[i >> 1] + (i & 1);
        }
        return ones;
    }
}

/// <summary>Sum of Two Integers without + or -.</summary>
public static class SumOfTwo
{
    /// <summary>a + b using only bit operations, with 32-bit signed wraparound.</summary>
    /// <param name="a">A 32-bit signed integer.</param>
    /// <param name="b">A 32-bit signed integer.</param>
    /// <returns>Their sum, wrapped like unchecked int addition.</returns>
    /// <example>SumOfTwo.GetSum(-2, 3) returns 1.</example>
    public static int GetSum(int a, int b)
    {
        // Invariant: a + b (as 32-bit ints) equals the true answer.
        // b is the carry. Its lowest 1 moves at least 1 column left each pass,
        // so after at most 32 passes it falls off bit 31 and b becomes 0.
        while (b != 0)
        {
            // Columns where both are 1 make a carry. << 1 moves it to the next
            // column. A carry out of bit 31 is dropped, like real hardware.
            int carry = (a & b) << 1;
            a ^= b;                             // column sums with no carry
            b = carry;                          // the carries still to add
        }
        return a;
    }
}

Recap

Where this goes next

Pattern 20, K-way Merge and Two Heaps, goes back to heaps. It covers the two heap moves the top-K page only names: merging many sorted lists, and keeping a running median. In C# both use PriorityQueue<TElement, TPriority>. The Python version of this page is here.