Bitwise Manipulation

Bitwise manipulation is a high-value interview skill because it lets you solve problems by working directly with the binary representation of numbers. This pattern appears frequently in questions involving odd and even checks, finding a unique number among duplicates, generating subsets, using masks, and storing small pieces of state efficiently. Once you know how to check, set, and clear a bit, many problems that look complicated become short and straightforward.

The main idea is simple: an integer is just a sequence of 0s and 1s in binary. Bitwise operators let you inspect or change those bits directly, and each operation takes constant time. That is why bitwise solutions are usually fast and often avoid the need for using extra arrays or hash maps.

What is bitwise manipulation?

Computers store data in memory as sequences of 0’s and 1’s, called bits. Bitwise manipulation means solving problems by operating directly on those bits using bitwise operators. Since processors support these operations natively, they are extremely fast, and they often lead to efficient solutions when a problem can be expressed in terms of binary representation or bit-level state changes.

Bitwise operations can be applied to two common categories of binary numbers:

• Unsigned binary numbers represent nonnegative integers only.
• Signed binary numbers represent both positive and negative integers, typically using two’s complement, where the leftmost bit affects the sign.

Conceptually, a bitwise operation works on a binary numeral (a bit string) and computes the result bit by bit. Instead of treating a number as a single decimal value, you treat it as a binary sequence and inspect or update specific positions.

Bitwise operations

Bitwise operations let you work directly with the bits of an integer, treating it as a sequence of 0s and 1s rather than a single value. This is useful in interviews because many problems become simpler when you can control individual bits, such as turning a flag on or off, checking whether a bit is set, or representing a small set of choices compactly. Bitwise operations are performed using a small set of operators, each with a specific job, such as combining bits, flipping them, or shifting them left or right.

Bitwise NOT

The bitwise NOT operator operates on a single bit and inverts it. Every 1 turns into 0, and every 0 turns into 1. The example below shows how this operator works:

Bitwise AND

The bitwise AND (&) operator compares two numbers bit by bit. A resultant bit becomes 1 only when both input bits at that position are 1. If either bit is 0, the result at that position is 0. The example below shows how this operator works:

Bitwise OR

The bitwise OR (|) operator compares two numbers bit by bit. The resultant bit becomes 1 if at least one of the input bits at that position is 1. It becomes 0 only when both bits are 0. The example below shows how this operator works:

Bitwise XOR

The bitwise XOR (^) operator compares two numbers bit by bit. A bit in the result becomes 1 only when the two input bits at that position are different (one is 0, and the other is 1). If the bits match, the result at that position is 0. The example below shows how this operator works:

Bitwise left shift

The bitwise left shift (<<) operator moves all bits in an unsigned binary number to the left by a given number of positions. The empty positions on the right are filled with 0s. Each single left shift doubles the value, so shifting left by n positions is the same as multiplying the number by 2ⁿ. The example below shows how a left shift works.

Bitwise right shift

The bitwise right shift (>>) operator moves all bits in an unsigned binary number to the right by a given number of positions. The empty positions on the left are filled with 0s. Each single right shift halves the value, so shifting right by n positions is the same as dividing the number by 2ⁿ (using integer division). The example below shows how a right shift works on an unsigned binary value.

Cyclic shifts move the bits of a binary number to the left or right, but unlike normal shifts, the bits that fall off one end are brought back on the other end. In other words, the bits wrap around instead of being replaced with zeros. The example below shows how a cyclic left shift works on an unsigned binary value.

Example: Power of Two

Let’s have a look at an example to understand bitwise manipulation.

Goal: Determine whether a given integer is a power of two.

A naive approach to solve this problem is to keep dividing the number by 2 and check whether you end exactly at 1. If the number is odd at any step, you can stop because it cannot be a power of two. While this works, it still performs repeated operations and depends on looping until the value shrinks, which can take multiple steps for large inputs.

Bitwise manipulation optimizes this with a simple observation: a power of two has exactly one 1 in its binary representation. If n is a power of two, subtracting 1 changes that 1 to 0 and turns all lower bits (the bits to the right of the single 1) into 1. When we compute n & (n - 1), that original 1 no longer overlaps with any 1 in n - 1, so the result is 0. So we can check the power of two in constant time, using O(1) extra space.

Let’s have a look at the following illustration to better understand this algorithm:

1 / 4

Python implementation

Now, let’s look at the optimized solution code for Power of Two problem.

def is_power_of_two(x):
    return x > 0 and (x & (x - 1)) == 0

# Driver code
def main():
    test_cases = [-512, 0, 1, 4, 123456]
    for i in range(len(test_cases)):
        result = "Yes" if is_power_of_two(test_cases[i]) else "No"
        print(f"{i+1}. \t Is {test_cases[i]} power of two? {result}.")
        print("-" * 100 + "\n")


if __name__ == "__main__":
    main()

What makes this a bitwise manipulation problem?

• The solution relies on a binary property of the number, not on scanning or comparing elements.
• Each step uses a bitwise operator (&) to directly test or transform bits instead of using extra loops or extra memory.
• The operation reduces the problem to a small fixed number of CPU-level checks.

Complexity analysis

• The time complexity of this algorithm is typically O(1) for single-number checks like “power of two” because we do a constant number of bitwise operations.
• The space complexity of this algorithm is O(1) extra space because we only use a few variables and no additional data structures.

When to use bitwise manipulation?

Bitwise manipulation is a good fit when the problem can be reduced to checking or updating bits directly. It works best when binary representation gives you a shortcut that avoids extra data structures or repeated scanning. The table below lists common signals that indicate bitwise manipulation is the right technique.

Identifying bitwise manipulation problems

Bitwise manipulation is often mistaken for “math tricks,” but the key is that the solution depends on bit-level reasoning, not just arithmetic shortcuts.

Why the confusion happens:

• Some solutions use division or modulo repeatedly, which is arithmetic and may require loops.
• Some solutions rely on memorized formulas without explaining the underlying bit behavior.
• Some solutions use bitwise operators randomly, without a clear bit-level invariant.

How to tell you are using the Bitwise Manipulation pattern:

• The binary insight is explicit: You can explain the bit property you are using (for example, “a power of two has exactly one set bit”).
• Operations target bits directly: You use masks or XOR to test, set, clear, or cancel bits intentionally.
• The operator choice is justified: You can explain why &, ^, or shifts are the correct tool for the required effect.

If these are not true, the code might still work, but it is not using bitwise manipulation in the way that gives it speed and clean reasoning.

Common mistakes and how to avoid them

Bitwise manipulation is compact, but small misunderstandings can break correctness. The most common mistakes include:

• Confusing bit positions: Bit 0 is the rightmost bit. Avoid it by consistently treating the least significant bit as position 0 and building masks with (1 << i).
• Forgetting parentheses in masks: 1 << i must be grouped when combined with other operators. Avoid it by always writing masks as (1 << i).
• Misusing NOT (~) in Python: ~x is not “just flip bits” in a finite width. Python integers are unbounded, so ~x behaves like -(x + 1). Avoid it by using ~ mainly as part of a mask, like x & ~mask, and by keeping your mask width clear when needed.
• Assuming shifts always match arithmetic for negatives: Right shifts on negative numbers can behave differently across languages. Avoid it by confirming whether inputs can be negative and, if they can, stating how your language handles shifts.
• Using bit tricks without explaining the why: Interviewers will ask you to justify identities like n & (n - 1). Avoid it by explaining the bit pattern change, not just the formula.

Interview tips

Some common interview tips when using bitwise manipulation include the following:

• Start by describing the binary insight: For example, “duplicates cancel under XOR” or “power of two has one set bit.”
• Use masks deliberately: Build masks with (1 << i) and explain what that bit position represents.
• Know the three core identities:
  • a ^ a = 0 (cancels duplicates)
  • n & (n - 1) removes the lowest set bit
  • n & -n isolates the lowest set bit
• State the complexity clearly: Each bitwise operation is constant time, and the overall runtime depends on whether you process one number (O(1)) or an array (O(n)).