Skip to content
Data Structures & Algorithms

Bit Manipulation interview questions and answers

40 questions, 34 with code. About 3 h 5 min to read them all.

By TestLab · Updated

Plan for an interview
40 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What does a bit represent in computing?

A bit is the smallest unit of digital information. It represents one of two binary states, conventionally 0 and 1; groups of bits encode numbers, characters, images, instructions, and other data.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Meaning and Representation

Computers represent data using sequences of binary digits. For example:

Decimal Binary
0 0000
1 0001
2 0010
4 0100
12 1100

In Python, format(12, '08b') produces 00001100, while bin(12) produces 0b1100.

A byte contains 8 bits and therefore has 256 possible values, conventionally numbered 0 through 255. Larger units depend on whether decimal or binary prefixes are intended:

Unit Exact size
KB 1,000 bytes
MB 1,000,000 bytes
GB 1,000,000,000 bytes
KiB 1,024 bytes
MiB 1,048,576 bytes
GiB 1,073,741,824 bytes

SI units such as KB and GB use decimal multiples. IEC units such as KiB and GiB use binary multiples. Some software and legacy documentation use the labels KB, MB, and GB for binary multiples, whereas storage manufacturers generally use decimal units.

Bitwise Operators

Bitwise operators examine or combine the binary representations of their operands:

Operator Operation Rule Example
& AND A result bit is 1 only when both input bits are 1 12 & 10 = 8
| OR A result bit is 1 when at least one input bit is 1 12 | 10 = 14
^ XOR A result bit is 1 when the input bits differ 12 ^ 10 = 6
~ NOT Inverts each bit in Python’s unbounded two’s-complement representation ~12 = -13
<< Left shift Moves bits left and inserts zeros 12 << 1 = 24
>> Right shift Moves bits right 12 >> 1 = 6

Useful bit tricks include:

  • x & (x - 1) clears the lowest set bit of a positive integer.

  • x & -x isolates the lowest set bit.

  • x ^ x is always 0 for one number.

  • x > 0 and (x & (x - 1)) == 0 checks whether x is a power of two.

  • int.bit_count() counts set bits in Python 3.10 and later.

For the AND operation, each bit is evaluated independently:

Bit position 4 3 2 1 0
12 0 1 1 0 0
10 0 1 0 1 0
12 & 10 0 1 0 0 0

The result is 01000 in binary, which equals 8 in decimal.

Complexity

For fixed-width integers, such as 32-bit or 64-bit machine integers, each bitwise operation takes O(1) time because the processor handles a fixed number of bits at once. It uses O(1) auxiliary space, excluding the input; no recursion stack is involved.

Python integers have arbitrary precision. In a bit-complexity model, bitwise operations on two n-bit integers generally require O(n) time and O(n) bits for the result or intermediate values. A left shift by s positions can produce up to n + s bits, so it requires O(n + s) time and O(n + s) bits of result space. A right shift requires O(n) time and up to O(n) bits of result space. These deterministic operations have the same best, average, and worst-case bounds. The original inputs are excluded from the space figures.

Common Pitfalls

  • Python integer overflow: Python integers do not overflow. For explicit 32-bit unsigned behavior, use value & 0xFFFFFFFF; to interpret that result as signed two’s complement, subtract 2**32 when it is at least 2**31.

  • Python NOT behavior: ~x equals -x - 1, so ~12 is -13.

  • Negative right shifts: Python uses arithmetic right shift for negative integers, preserving the sign.

  • Negative shift counts: Shift counts must be non-negative.

  • Power-of-two check: 0 is not a power of two, so the x > 0 condition is necessary.

  • Bit versus byte: A bit is one binary digit; a byte contains 8 bits.

2

What is a byte in computing and data storage?

A byte is a group of eight bits and is the basic addressable unit of memory in most computer systems. It can represent (2^8 = 256) distinct values, ranging from 0 to 255 when treated as unsigned.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definition and Representation

Eight bits form one byte:

Bit position 7 6 5 4 3 2 1 0
Example value 1 0 1 0 0 1 0 0

The example represents the binary value 10100100, which equals decimal 164. In Python 3.12, format(164, "08b") returns '10100100'.

A byte can represent:

  • Unsigned data: 0 through 255.

  • Signed data: typically -128 through 127 using two’s complement.

  • Characters: one byte in ASCII, but not necessarily one byte in modern encodings such as UTF-8.

  • Arbitrary data: portions of numbers, images, audio, compressed files, or network packets.

Although “byte” historically meant a machine-dependent unit of storage, it conventionally means eight bits today. The term octet always means exactly eight bits.

Bytes Versus Bits

A bit stores one binary value: either 0 or 1. A byte contains eight such values.

Unit Bytes Bits
Bit 1/8 1
Byte 1 8
Kilobyte (KB) 1,024 8,192
Megabyte (MB) 1,048,576 8,388,608

The commonly used abbreviations such as KB and MB historically implied binary multiples, but storage products sometimes use decimal multiples. For example, one megabyte is conventionally 1,048,576 bytes, while some manufacturers label 1,000,000 bytes as one megabyte.

Bytes in Python 3.12

Python’s bytes type is an immutable sequence of byte values:

  • len(b"hello") returns 5.

  • b"hello"[0] returns 101, the integer value of the first byte.

  • Iterating over a bytes object produces integers, unlike iterating over str, which produces Unicode strings.

  • bytes objects support slicing and concatenation, both of which create new objects.

A Python str is not stored as bytes. Encoding converts text into a bytes object using an encoding such as UTF-8:

  • b"A" is one byte.

  • "A".encode("utf-8") is also one byte.

  • "€".encode("utf-8") is three bytes.

  • "é".encode("utf-8") is two bytes.

Bitwise Operators on Bytes

Bitwise operators work at the bit level:

Operator Meaning Example
& Bitwise AND 0b1100 & 0b1010 → 0b1000
| Bitwise OR 0b1100 | 0b1010 → 0b1110
^ Bitwise XOR 0b1100 ^ 0b1010 → 0b0110
~ Bitwise NOT ~0 is -1 in Python
<< Shift bits left 0b0011 << 2 → 0b1100
>> Shift bits right 0b1100 >> 2 → 0b0011

For example, 0b1100 & 0xFF preserves the low eight bits. This is commonly used when extracting a byte from a larger integer.

Python integers have arbitrary precision, so ~x equals -x - 1 rather than being limited to a fixed-width complement. To emulate unsigned 32-bit behavior, mask the result with 0xFFFFFFFF.

Complexity

  • Single-byte access: O(1) time and O(1) additional space because the byte’s position can be calculated directly.

  • Copying or hashing an n-byte object: O(n) time and O(n) additional space for the resulting copy.

  • Fixed-width bitwise operation: O(1) time and O(1) additional space.

  • Bitwise operation on a k-bit Python integer: O(k) time and space because Python must process the integer’s underlying machine words.

Common Pitfalls

  • A character is not necessarily one byte; UTF-8 characters can occupy multiple bytes.

  • bytes indexing returns an integer, while str indexing returns a one-character string.

  • Binary and decimal storage units may differ by about 2.4%.

  • Bitwise NOT depends on integer width and signedness in fixed-width languages; Python’s ~ uses arbitrary-precision semantics.

  • Python integers do not overflow, unlike fixed-width integer types in languages such as C or Java.

  • Byte order matters when interpreting multi-byte values: big-endian places the most significant byte first, while little-endian places it last.

3

What is a bitwise operation in computer programming?

A bitwise operation manipulates the individual binary digits, or bits, of an integer. These operations are commonly used for efficient arithmetic, flag management, permissions, hashing, and low-level algorithms.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Bitwise Operations Work

Each bit is either 0 or 1. Operators combine corresponding bits from their operands:

  • & — bitwise AND: A result bit is 1 only when both corresponding bits are 1.

  • | — bitwise OR: A result bit is 1 when at least one corresponding bit is 1.

  • ^ — bitwise XOR: A result bit is 1 when the corresponding bits differ.

  • ~ — bitwise NOT: Inverts each bit within the applicable representation.

  • << — left shift: Moves bits left, equivalent to multiplication by a power of two when no overflow occurs.

  • >> — right shift: Moves bits right and discards low-order bits; in Python, shifting a nonnegative integer right by k is equivalent to floor division by 2**k.

In Python, format(12, "08b") returns "1100", while format(10, "08b") returns "1010". The bit-by-bit result of 12 & 10 is:

Bit position 3 2 1 0
12 1 1 0 0
10 1 0 1 0
12 & 10 1 0 0 0

The result is 1000 in binary, which is 8 in decimal.

Python integers have arbitrary precision and therefore do not overflow. Because Python represents negative integers using infinite sign extension, ~x equals -x - 1; for example, ~12 is -13. In a fixed-width two’s-complement representation, ~ instead inverts only the bits within that width. Masking with 0xFFFFFFFF isolates an integer’s low 32 bits.

Common Bitwise Tricks

  • Clear the lowest set bit: x & (x - 1) removes the rightmost 1 bit.

  • Isolate the lowest set bit: x & -x keeps only the rightmost 1 bit.

  • Toggle selected bits: x ^ mask inverts the bits covered by mask.

  • Swap two values without a temporary: left, right = left ^ right, right ^ left followed by left, right = right ^ left, left ^ right.

  • Check whether a positive integer is a power of two: x > 0 and x & (x - 1) == 0.

  • Count set bits: x.bit_count() is available in Python 3.10 and later.

  • Generate subsets with a bitmask: Each mask from 0 to 2**n - 1 represents one subset of n elements.

Complexity

For fixed-width integers, such as 32-bit or 64-bit values:

  • Time: O(1) in the best, average, and worst cases because the number of processed bits is fixed.

  • Space: O(1), including the fixed-sized result and excluding no meaningful input-size variation.

For Python arbitrary-precision integers containing b bits:

  • Time: O(b) in the average and worst cases for a full-width bitwise operation. The best case can be O(1) for specialized cases such as AND with zero.

  • Space: O(b) when the newly produced integer is included; O(1) auxiliary space beyond that result. The input operands are not counted.

A left shift by k can produce approximately b + k bits, so its time and result space can be O(b + k). A right shift cannot increase the integer’s magnitude and takes O(b) time in the worst case.

Common Pitfalls

  • ^ is XOR, not exponentiation: Use ** for exponentiation in Python.

  • ~ is not Boolean negation: ~x performs bit inversion, while not x converts a value to a Boolean.

  • Mind operator precedence: Use parentheses to make expressions such as a & b == c unambiguous.

  • Mind fixed-width semantics: Shifts, signedness, and overflow follow the type’s width in fixed-width languages.

  • Remember that Python does not overflow: Very large integers work correctly but require more time and memory.

  • Count shift positions in bits: x << 4 shifts by four bit positions, not four numeric units.

  • Common follow-up questions: Interviewers often ask about setting, clearing, and toggling flags, checking powers of two, counting set bits, generating subsets, or applying an XOR-based single-number algorithm.

4

Where are bitwise operators used in real-world systems?

Bitwise operators are used to inspect, combine, mask, and transform individual bits in bit-level representations. They are widely used in operating systems, networking, databases, compression, cryptography, hardware drivers, hash tables, and performance-sensitive algorithms.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How They Work

Each operator processes the binary representation of its operands:

  • & (AND): A result bit is 1 only when both input bits are 1. It is used for flag checks and selecting fields with a mask.

  • | (OR): A result bit is 1 when either input bit is 1. It combines flags or sets selected bits.

  • ^ (XOR): A result bit is 1 when the input bits differ. It toggles bits, performs parity checks, and can exchange the values of two distinct variables without a temporary.

  • ~ (NOT): Complements the bits. In fixed-width arithmetic, it inverts every bit in that width. In Python, ~x equals -x - 1; Python integers use arbitrary precision rather than fixed-width two’s-complement overflow.

  • << (left shift): Shifts bits left. Without overflow, x << k multiplies an integer by 2**k.

  • >> (right shift): Shifts bits right. For nonnegative Python integers, it is equivalent to floor division by 2**k; for negative integers, Python uses an arithmetic shift that preserves the sign.

For example, format(12, '08b') produces 00001100, while format(10, '08b') produces 00001010. The results are 12 & 10 = 8, 12 | 10 = 14, and 12 ^ 10 = 6.

Real-World Applications

Application Operators Example
File permissions &, | Unix permission bits represent read, write, and execute access.
Network protocols &, |, ^, <<, >> IPv4 addresses, subnet masks, and packet headers are represented and interpreted as bit fields.
Database indexes &, | Bitmap indexes store matching positions as bits, allowing query results to be combined with bitwise operations.
Compression &, |, ^, <<, >> Bit packing stores compact encodings; simple schemes may combine XOR with bit shifts.
Cryptography &, ^, <<, >> Ciphers and hash functions use masks, permutations, rotations, shifts, and XOR in their rounds. XOR alone is not encryption.
Hardware and drivers &, |, <<, >> Device registers expose controls and status through individual bits.
Hash tables & Some power-of-two-sized tables use hash & (capacity - 1) for initial bucket selection, followed by collision handling.
Low-level algorithms &, ^ Subset enumeration, parity detection, Gray codes, and compact state representations use bit manipulation.

A common flag pattern assigns one bit to each capability: READ = 1 << 0, WRITE = 1 << 1, and EXECUTE = 1 << 2. READ | WRITE enables both flags, while permissions & READ checks whether reading is enabled.

Bit-by-Bit Example

For x = 12 (1100₂) and mask = 10 (1010₂), x & mask keeps only bits enabled by the mask:

Bit position x mask x & mask
3 1 1 1
2 1 0 0
1 0 1 0
0 0 0 0

The result is 1000₂, which equals 8. The mask therefore isolates the fields relevant to the operation.

Complexity

  • Fixed-width integers: Every bitwise operation has O(1) best-case, average-case, and worst-case time because the number of bits is constant. It uses O(1) auxiliary space for the result; the inputs are not counted.

  • Python arbitrary-precision integers: For operands containing b bits and internal words of w bits, an operation generally takes O(⌈b/w⌉) time and O(⌈b/w⌉) auxiliary space for the result. The original inputs are not counted.

  • Submask enumeration: Visiting every submask of a fixed-width mask containing k set bits takes O(2^k) time and O(1) auxiliary space, excluding the input mask. With arbitrary-precision masks, the time is O(2^k · ⌈b/w⌉).

  • Hash-table lookup: With a good hash function and controlled load factor, lookup is O(1) average time and O(n) worst-case time because of collisions.

Common Pitfalls

  • Signed right shifts: Python preserves the sign when right-shifting a negative integer. For a logical 32-bit right shift, use (x & 0xFFFFFFFF) >> k.

  • Precedence: Python shifts have lower precedence than arithmetic but higher precedence than comparisons. Parentheses make intent clearer.

  • Overflow: Python integers do not overflow, unlike fixed-width integers in languages such as Java or C++.

  • Mask width: ~x is not a 32-bit complement in Python. Apply & 0xFFFFFFFF when retaining only the lowest 32 bits.

  • Power-of-two check: Use x > 0 and (x & (x - 1)) == 0; the positivity test prevents zero from being accepted.

  • Common follow-up: Interviewers may ask about setting or clearing a bit, counting set bits with int.bit_count(), reversing bits, or isolating the lowest set bit with x & -x.

5

How does bitwise AND determine whether a number is odd or even?

A bitwise AND operation compares corresponding bits of two integers and produces 1 at a position only when both input bits are 1. To determine parity, AND the number with 1: its least significant bit is 1 for odd numbers and 0 for even numbers.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For each bit position, the bitwise AND operator & follows this rule:

Left bit Right bit Result
0 0 0
0 1 0
1 0 0
1 1 1

The least significant bit, or LSB, stores the remainder when dividing an integer by 2:

  • (number & 1) == 1: the number is odd.

  • (number & 1) == 0: the number is even.

For example, 13 & 1 can be examined bit by bit:

Bit position 13 1 13 & 1
3 (8s) 1 0 0
2 (4s) 1 0 0
1 (2s) 0 0 0
0 (1s) 1 1 1

The result is 1, so 13 is odd.

Important edge cases:

  • 0 is even because 0 & 1 is 0.

  • Negative integers follow the same test. Python’s bitwise operations behave as though integers have an infinite two’s-complement sign extension, so -3 & 1 is 1 and -2 & 1 is 0.

  • The same masking technique can test or clear other selected bits.

Common Bitwise Operators

Operator Meaning Example
& Bitwise AND 12 & 10 → 1100 & 1010 → 1000 (8)
‘ ‘ Bitwise OR ‘12 10→1100 1010→1110(14`)
^ Bitwise XOR 12 ^ 10 → 1100 ^ 1010 → 0110 (6)
~ Bitwise NOT Python defines ~x as -x - 1, so ~12 is -13
<< Left shift 12 << 1 → 11000 (24)
>> Right shift 12 >> 2 → 11 (3)

Python integers have arbitrary precision and therefore do not overflow. When an unsigned 32-bit representation is required, x & 0xFFFFFFFF produces the low 32 bits of the two’s-complement representation.

Complexity

  • Fixed-width integers: The parity decision takes O(1) time in the best, average, and worst cases because only one bit is inspected. It uses O(1) auxiliary space, excluding the input, and has no recursion stack.

  • Python arbitrary-precision integers: In CPython 3.12, masking a nonnegative int with 1 takes O(1) time and auxiliary space because the result has one digit. For a negative int, constructing the two’s-complement representation can take O(b) time and temporary space, where b is the operand’s bit length. Thus the best case is O(1), the worst case is O(b), and the average depends on the workload’s distribution of positive and negative values. The input storage itself is not counted.

  • Formatting the binary diagnostic: format(x, '08b') takes O(b) time and output space because it constructs a string containing the binary digits.

Code Example

def parity(number: int) -> str:
    """Return "odd" or "even" using the number's least significant bit."""
    return "odd" if (number & 1) == 1 else "even"


if __name__ == "__main__":
    number = 13
    print(
        f"{format(number, '08b')} & {format(1, '08b')} = "
        f"{format(number & 1, '08b')}"
    )  # 00001101 & 00000001 = 00000001
    print(parity(number))  # odd

Common Pitfalls

  • Use &, not Python’s logical and; and returns an operand, while & performs a bitwise operation.

  • Write parentheses around comparisons such as (number & 1) == 1 to make the intended grouping explicit.

  • Do not use shifts as substitutes for multiplication or division when handling negative values; Python’s right shift on a negative integer is an arithmetic shift.

  • In fixed-width languages, distinguish signed from unsigned behavior and mask explicitly when an unsigned 32-bit result is required.

  • Interviewers may also ask about related tricks: x & (x - 1) clears the lowest set bit, x & -x isolates it, and x ^ x produces zero.

6

How does bitwise OR work in Python?

The bitwise OR operator (|) combines two integers bit by bit, producing a 1 whenever either operand has a 1 in that position. It is commonly used to combine independent flags or set multiple bits in a bitmask.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Bitwise OR examines corresponding bits independently:

Bit position 7 6 5 4 3 2 1 0
12 0 0 0 0 1 1 0 0
10 0 0 0 0 1 0 1 0
12 | 10 0 0 0 0 1 1 1 0

Therefore, 12 | 10 is 00001110 in binary, which is 14 in decimal.

For example, combining read and write permissions works naturally:

  • Read permission: 0b0100

  • Write permission: 0b1000

  • Combined permissions: 0b0100 | 0b1000 == 0b1100

Bitwise Operator Reference

Using 12 (00001100) and 10 (00001010):

Operator Operation Binary result Decimal result
& AND 00001000 8
| OR 00001110 14
^ XOR 00000110 6
~ Bitwise NOT ...11110011 -13
<< Left shift 00011000 24
>> Right shift 00000110 6
  • AND (&): keeps a bit only when both operands have it.

  • OR (|): keeps a bit when either operand has it.

  • XOR (^): keeps a bit when exactly one operand has it.

  • NOT (~): inverts every bit.

  • Left shift (<<): moves bits left, multiplying by two for each position.

  • Right shift (>>): moves bits right, dividing by two for each position.

Python Behavior and Edge Cases

  • Zero identity: x | 0 == x.

  • Idempotence: x | x == x.

  • Commutativity: x | y == y | x.

  • No carry propagation: 1 | 1 is 1, not binary addition’s 10.

  • Negative numbers: Python integers use arbitrary precision with infinite two’s-complement semantics. Consequently, 12 | -1 is -1.

  • Arbitrary precision: Python integers have no fixed bit width and do not overflow.

  • Scalar operation: empty or multi-element collections do not apply; operands must be integers.

  • Duplicate values: duplicates are irrelevant because OR only examines individual bit positions.

Code Example

def bitwise_or(left: int, right: int) -> int:
    """Return the bitwise OR of two integers."""
    return left | right


result = bitwise_or(12, 10)
print(result)  # 14

The equivalent expression can also be inspected in binary:

value = 12 | 10
print(format(value, "08b"))  # 00001110

Complexity

For operands containing at most n bits:

  • Time: O(n) best, average, and worst case, because Python may process every bit of an arbitrary-precision integer.

  • Space: O(n) additional space for the newly allocated result; the input operands are not counted.

  • Fixed-width languages: When integers have a fixed width, such as 32-bit integers, the operation is O(1) time and O(1) additional space.

Common Pitfalls

  • Do not confuse | with or: | performs bitwise OR and returns an integer, while or returns an operand based on truthiness.

  • Remember that OR does not add: overlapping set bits do not produce a carry.

  • Use parentheses for clarity: Python’s precedence can make mixed expressions harder to read.

  • Choose the correct operator: use | to set flags, & to test flags, and ^ to toggle flags.

7

How does bitwise XOR work and what is it commonly used for?

Bitwise XOR (^) compares corresponding bits in two integers and produces 1 wherever the bits differ. It is useful for toggling flags, swapping values, calculating parity, canceling duplicate values, and identifying differing bits.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How XOR Works

XOR operates independently on each bit:

  • 0 ^ 0 = 0

  • 0 ^ 1 = 1

  • 1 ^ 0 = 1

  • 1 ^ 1 = 0

For example, 12 ^ 10 compares their binary representations:

Bit position 7 6 5 4 3 2 1 0
12 0 0 0 0 1 1 0 0
10 0 0 0 0 1 0 1 0
12 ^ 10 0 0 0 0 0 1 1 0

The result is 00000110, which equals 6.

XOR also follows these useful identities:

  • x ^ x = 0

  • x ^ 0 = x

  • XOR is associative and commutative, so operand order does not matter.

  • a ^ b ^ b = a

Bitwise Operators Overview

Operator Operation Example in Python
& Bitwise AND: 1 only when both bits are 1 12 & 10 == 8
| Bitwise OR: 1 when either bit is 1 12 | 10 == 14
^ Bitwise XOR: 1 when the bits differ 12 ^ 10 == 6
~ Bitwise NOT: inverts every bit ~12 == -13
<< Shift bits left, multiplying by powers of two 12 << 1 == 24
>> Shift bits right, dividing by powers of two 12 >> 1 == 6

Python integers have arbitrary precision. Consequently, ~x is exactly -x - 1 rather than a fixed-width complement. To retain only the low 32 bits of an XOR result, use:

result = (left ^ right) & 0xFFFFFFFF

Common Uses

  • Toggle a flag: flags ^= mask sets a bit if it was clear and clears it if it was set.

  • Swap two distinct values: the classic sequence is a ^= b, then b ^= a, then a ^= b. In ordinary code, tuple assignment is clearer and avoids aliasing issues.

  • Find a unique value: XOR all elements when every duplicate appears an even number of times. Duplicate pairs cancel because x ^ x == 0.

  • Calculate parity: value.bit_count() & 1 returns 0 for even parity and 1 for odd parity.

  • Measure Hamming distance: (left ^ right).bit_count() counts the bit positions where the values differ.

  • Build prefix XORs: each prefix combines all earlier values, allowing repeated range-XOR queries with constant-time prefix lookups.

  • Create simple checksums: XOR can detect an odd number of changed bits, but it is not a cryptographic hash and does not reliably detect arbitrary corruption.

Complexity

For fixed-width integers:

  • Best, average and worst-case time: O(1), because the number of bits is fixed.

  • Auxiliary space: O(1); the input is not copied or modified, and the recursion stack is O(1).

For Python’s arbitrary-precision integers with b bits:

  • Best, average and worst-case time: O(b), since every bit may need processing.

  • Space: O(b) to materialize the result. The input is not counted because it is neither copied nor modified.

  • Recursion stack: O(1).

Scanning n fixed-width values with a running XOR takes O(n) time and O(1) auxiliary space.

Code Example

def xor_with_trace(left: int, right: int) -> tuple[int, list[str]]:
    """Compute an 8-bit XOR and show each bit calculation."""
    if not (0 <= left <= 0xFF and 0 <= right <= 0xFF):
        raise ValueError("Both values must be between 0 and 255.")

    result = 0
    trace: list[str] = []

    for bit_index in range(7, -1, -1):
        left_bit = (left >> bit_index) & 1
        right_bit = (right >> bit_index) & 1
        result_bit = left_bit ^ right_bit
        result |= result_bit << bit_index

        trace.append(
            f"bit {bit_index}: "
            f"{left_bit} ^ {right_bit} = {result_bit}"
        )

    return result, trace


print(xor_with_trace(12, 10))
# (6, ['bit 7: 0 ^ 0 = 0', 'bit 6: 0 ^ 0 = 0',
#      'bit 5: 0 ^ 0 = 0', 'bit 4: 0 ^ 0 = 0',
#      'bit 3: 1 ^ 1 = 0', 'bit 2: 1 ^ 0 = 1',
#      'bit 1: 0 ^ 1 = 1', 'bit 0: 0 ^ 0 = 0'])

Common Pitfalls

  • Confusing XOR with OR: ^ produces 1 only when the bits differ.

  • Assuming ~x is simply 255 - x; Python’s unbounded representation makes ~x == -x - 1.

  • Using the XOR swap when both variables reference the same object, which can set it to zero.

  • Using the unique-number XOR pattern without the guarantee that duplicates occur in pairs.

  • Forgetting that signed right shifts and fixed-width overflow rules vary by language; Python integers do not overflow.

  • Interviewers may ask about XOR’s algebraic identities, XOR prefixes, Hamming distance, or how the operation can implement a binary search.

8

How do you set, toggle, and clear a bit in Python?

A bit mask identifies one zero-based bit position. Create the mask with 1 << bit, then use bitwise OR to set the bit, XOR to toggle it, or AND with the complemented mask to clear it.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For a target bit position bit, the mask is:

mask = 1 << bit
  • Set the bit: number | mask

  • Toggle the bit: number ^ mask

  • Clear the bit: number & ~mask

Bit positions start at 0 for the least significant, or rightmost, bit. For example, 1 << 3 produces 0b1000, selecting bit 3.

Operator Reference

Operator Name Behavior Binary example
& AND Keeps a bit set only when both operands have it set 1010 & 0110 = 0010
| OR Sets a bit when either operand has it set 1010 | 0110 = 1110
^ XOR Toggles a bit when the operands differ 1010 ^ 0110 = 1100
~ NOT Inverts every bit ~0b1010 = -0b1011
<< Left shift Moves bits left and inserts zeroes 0b0001 << 3 = 0b1000
>> Right shift Moves bits right and discards them 0b1010 >> 1 = 0b0101

In Python, integers have arbitrary precision and use an infinite two’s-complement model. Consequently, ~x evaluates to -x - 1, and integer overflow does not occur.

Step-by-Step Example

Toggle bit 1 of 0b1010:

  1. Create the mask: 1 << 1 = 0b0010.

  2. Apply XOR: 0b1010 ^ 0b0010.

  3. Read the result from right to left:

Bit position 3 2 1 0
Original 1 0 1 0
Mask 0 0 1 0
XOR result 1 0 0 0

The result is 0b1000, or decimal 8.

Code Example

def set_bit(number: int, bit: int) -> int:
    """Return number with the zero-based bit set to 1."""
    if bit < 0:
        raise ValueError("bit must be non-negative")
    return number | (1 << bit)


def toggle_bit(number: int, bit: int) -> int:
    """Return number with the zero-based bit inverted."""
    if bit < 0:
        raise ValueError("bit must be non-negative")
    return number ^ (1 << bit)


def clear_bit(number: int, bit: int) -> int:
    """Return number with the zero-based bit set to 0."""
    if bit < 0:
        raise ValueError("bit must be non-negative")
    return number & ~(1 << bit)


if __name__ == "__main__":
    value = 0b1010

    print(format(set_bit(value, 2), "08b"))    # 00001110
    print(format(toggle_bit(value, 1), "08b"))  # 00001000
    print(format(clear_bit(value, 3), "08b"))   # 00000010

These functions do not mutate the input because Python integers are immutable. They handle zero and negative integer values; only a negative bit index is invalid.

To restrict results explicitly to an unsigned 32-bit value, apply & 0xFFFFFFFF to the final result.

Complexity

For fixed-width integers such as 32-bit or 64-bit values:

  • Best, average, and worst-case time: O(1) because each operation processes a constant number of machine words.

  • Auxiliary space: O(1), excluding the input. There is no recursion stack.

For Python’s arbitrary-precision integers, let k be the number of machine words required for the number and mask:

  • Best, average, and worst-case time: O(k) because shifting, complementing, and combining integers operate across their machine words.

  • Auxiliary space: O(k) for the mask and intermediate or returned integers, excluding the original input.

Common Pitfalls and Interview Tips

  • Wrong indexing: Bit 0 is the least significant bit; there is no one-based indexing.

  • Incorrect clear operation: number & mask preserves only the selected bit. Use number & ~mask to clear it.

  • XOR semantics: XOR toggles the current value; it does not always set the bit to 1.

  • Python integer width: Python does not overflow. Use & 0xFFFFFFFF only when a specific 32-bit representation is required.

  • Invalid indexes: Reject negative bit positions before shifting, since Python would otherwise raise ValueError.

  • Common follow-up: Interviewers may ask how to count set bits with int.bit_count() or test whether a positive integer is a power of two using value & (value - 1) == 0.

9

What is bit masking, and how do you create an nth-bit mask?

A bit mask is a bit pattern used to select, clear, set, or test specific bits in an integer. To isolate the zero-based nth bit, create a mask with 1 << n and apply it with bitwise AND: value & (1 << n).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Bitwise operations treat integers as sequences of binary digits. A mask contains 1 in the positions you want to preserve and 0 elsewhere.

With zero-based indexing:

  • n = 0 refers to the least significant bit.

  • n = 1 refers to the second least significant bit.

  • 1 << n creates a mask containing exactly one set bit at position n.

  • value & mask preserves the selected bit and clears every other bit.

To normalize the extracted bit to either 0 or 1, shift it back to the least significant position:

(value & (1 << n)) >> n

Python Bitwise Operators

  • & — bitwise AND: A result bit is 1 only when both input bits are 1.

  • | — bitwise OR: A result bit is 1 when either input bit is 1.

  • ^ — bitwise XOR: A result bit is 1 when the input bits differ.

  • ~ — bitwise NOT: In Python, ~x equals -x - 1; for example, ~5 == -6.

  • << — left shift: x << n moves each bit n positions left, multiplying by 2**n while allowing room for new bits.

  • >> — right shift: x >> n moves each bit n positions right, dividing by 2**n with Python’s floor behavior.

Useful related tricks include:

  • For nonzero x, x & (x - 1) clears the lowest set bit.

  • For nonzero x, x & -x isolates the lowest set bit.

  • x ^ x is 0 because identical bits cancel.

  • A positive integer is a power of two when x & (x - 1) == 0.

  • x.bit_count() counts set bits in Python 3.10 and later.

Creating and Tracing the Mask

For value = 40 and n = 3:

Step Binary result Meaning
Original value 00101000 Decimal 40
Create mask with 1 << 3 00001000 Select bit 3
Apply value & mask 00001000 Clear all other bits
Shift right by 3 00000001 Normalize to 0 or 1

Python integers use arbitrary precision, so they do not overflow. To retain only the low 32 bits as an unsigned value, use value & 0xFFFFFFFF. To interpret that bit pattern as signed two’s complement, subtract 1 << 32 when bit 31 is set; masking alone produces an unsigned residue.

Complexity

For fixed-width machine integers, bit creation, masking, and shifting each take O(1) time.

  • Best case: O(1) time.

  • Average case: O(1) time.

  • Worst case: O(1) time.

  • Space: O(1), excluding the input and including the output.

For arbitrary-precision Python integers, let B be the maximum bit length of the value and mask, and let w be the number of bits in an internal big-integer digit. The operations take O(⌈B / w⌉) time and peak additional space. The input is excluded from the space calculation; the mask and intermediate results are included. These cases remain the same across best, average, and worst inputs.

Code Example

def isolate_nth_bit(value: int, n: int) -> int:
    """Return the zero-based nth bit of value as either 0 or 1."""
    if n < 0:
        raise ValueError("Bit position n must be non-negative")

    mask = 1 << n
    return ((value & mask) >> n) & 1


print(isolate_nth_bit(40, 3))  # Expected output: 1

The function supports n = 0, large bit positions subject to available memory, and negative integer values. An excessively large n may allocate a correspondingly large mask.

Common Pitfalls

  • Indexing mismatch: 1 << n uses zero-based indexing. For a one-based position n, use 1 << (n - 1).

  • Losing the bit position: value & mask preserves the bit at its original position; shift afterward only if you want 0 or 1.

  • Python NOT assumptions: ~x produces -x - 1, not merely the reversal of a fixed-width number.

  • Negative bit positions: 1 << -1 raises an error, so validate n as shown.

  • Fixed-width behavior: In fixed-width languages, shifts at the type’s width boundary can truncate values or have language-specific behavior.

  • Common follow-up: Interviewers may ask how to test a bit, set a bit with value | (1 << n), or clear one with value & ~(1 << n).

10

How do left and right bit shifts work?

Bitwise shifts move the binary representation of an integer left or right by a specified number of bit positions. The left operator << shifts toward more-significant bits, while the right operator >> shifts toward less-significant bits.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How They Work

  • x << k: Moves each bit in x left by k positions.

  • The leftmost bits are discarded in a fixed-width machine.

  • Zero bits fill the vacated positions on the right.

  • Mathematically, x << k equals x * 2**k.

  • Python integers grow to hold the result rather than overflowing.

  • x >> k: Moves each bit in x right by k positions.

  • The rightmost bits are discarded.

  • Zero bits fill the vacated positions on the left for non-negative integers.

  • For positive integers, x >> k equals x // 2**k.

  • Python uses arithmetic right shifts for negative integers, preserving the sign. Therefore, -8 >> 1 is -4, not -3.

For example, starting with 0b00100000:

Bit position 7 6 5 4 3 2 1 0
Original 0 0 1 0 0 0 0 0
After << 2 1 0 0 0 0 0 0 0
After >> 2 0 0 0 0 1 0 0 0

Thus, 0b00100000 << 2 is 0b10000000, while 0b00100000 >> 2 is 0b00001000.

Bitwise Operator Reference

Using x = 0b1100 and mask = 0b1010:

Operator Name Result Purpose
x & mask AND 0b1000 Keeps bits set in both operands
x | mask OR 0b1110 Keeps bits set in either operand
x ^ mask XOR 0b0110 Returns set bits present in exactly one operand
~x NOT -13 Inverts every bit
x << k Left shift 0b11000 Moves bits toward the high-order end
x >> k Right shift 0b110 Moves bits toward the low-order end

In Python, ~x equals -x - 1 because Python integers use an unbounded two’s-complement representation.

Useful Bit Tricks

  • Clear the lowest set bit: x & (x - 1) removes the rightmost 1.

  • Isolate the lowest set bit: x & -x leaves only the rightmost 1.

  • Clear a single number: x ^ x equals 0.

  • Check whether a positive integer is a power of two: x > 0 and (x & (x - 1)) == 0.

  • Count set bits: x.bit_count() counts 1 bits in Python 3.10 and later.

These operations are useful for clearing flags, checking binary properties, and implementing bit masks.

Complexity

For a fixed-width machine integer, a shift is a constant-time operation. Python uses arbitrary-precision integers, so its actual cost depends on the number of bits.

Representation and operation Time Space Reason
Fixed-width integer O(1) best, average, and worst O(1) One machine-word operation
Python left shift, n-bit input and k positions O(n + k) best, average, and worst O(n + k) bits for the result Python must create and populate a larger integer
Python right shift, n-bit input O(n) best, average, and worst O(n) bits for the result Python must process the integer’s digit representation

Under the conventional definition, auxiliary space beyond the returned integer is O(1). The input itself is not counted, and there is no recursion stack.

Common Pitfalls

  • Expecting overflow: Python integers do not overflow. To emulate unsigned 32-bit behavior, mask the result with x & 0xFFFFFFFF.

  • Forgetting arithmetic shifts: Python’s >> rounds negative results toward negative infinity rather than truncating toward zero.

  • Ignoring precedence: Use parentheses when combining shifts with arithmetic, such as x << (1 + 1).

  • Assuming ~x is limited to 32 bits: Python returns -x - 1; mask it with 0xFFFFFFFF when emulating a fixed-width complement.

  • Losing shifted-out bits: In fixed-width languages, capture important high bits with a mask before shifting.

  • Creating huge integers: A large left shift can consume substantial memory even though Python has no integer overflow.

11

What differs between >> and >>> right-shift operators?

Right shift (>>) preserves the sign bit by propagating it to the right, while the unsigned right shift (>>>) fills the vacated positions with zeros. Python 3.12 supports >> but not >>>; Java, JavaScript, and C# provide both operators with fixed-width behavior.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Behavior

  • >> — arithmetic right shift: Copies the sign bit into the positions exposed by the shift.

  • For a positive value, it is equivalent to dividing by a power of two.

  • For a negative Python integer, it behaves like floor division by that power of two.

  • >>> — logical right shift: Shifts zero bits into the exposed positions.

  • In Java, an int result contains 32 bits and is always nonnegative.

  • A long version operates on 64 bits.

  • In JavaScript, bitwise operands are converted to 32-bit values.

For example, shifting positive 8 produces 4 with either operator because its sign bit is zero:

8 >> 1   # 4

The difference appears when the sign bit is set.

Bitwise Operator Reference

Using 8 = 00001000 and 10 = 00001010:

Expression Binary operation Result
8 & 10 00001000 & 00001010 8
8 | 2 00001000 | 00000010 10
8 ^ 3 00001000 ^ 00000011 11
~8 Invert every bit -9
8 << 1 00001000 << 1 16
8 >> 1 00001000 >> 1 4

In Python, ~x == -x - 1. Python integers have arbitrary precision and do not overflow.

Worked 32-Bit Example

For the signed 32-bit value -8:

Input:       11111111 11111111 11111111 11111000

>> 1:        11111111 11111111 11111111 11111100  = -4
>>> 1:       01111111 11111111 11111111 11111100  = 2147483644

The arithmetic shift retains the leading 1, while the logical shift replaces it with 0.

Common related tricks include:

  • x & (x - 1) clears the lowest set bit.

  • x & -x isolates the lowest set bit.

  • x ^ x is always 0.

  • x > 0 and x & (x - 1) == 0 tests whether x is a power of two.

  • int.bit_count() counts set bits in Python 3.10 and later.

Code Example

This Python function emulates Java-style 32-bit arithmetic and logical right shifts:

MASK_32 = 0xFFFFFFFF
SIGN_32 = 0x80000000


def right_shift_32(value: int, shift: int, *, logical: bool) -> int:
    """Apply a 32-bit arithmetic or logical right shift to an integer."""
    if not 0 <= shift <= 31:
        raise ValueError("shift must be between 0 and 31")

    unsigned = value & MASK_32

    if logical:
        return unsigned >> shift

    signed = unsigned if unsigned < SIGN_32 else unsigned - 0x100000000
    return signed >> shift


print(right_shift_32(-8, 1, logical=False))  # -4
print(right_shift_32(-8, 1, logical=True))   # 2147483644
print(format(8, "08b"))                     # 00001000

Complexity and Edge Cases

  • Fixed-width 32-bit operation: best, average, and worst time are O(1) because only a fixed number of bits are processed.

  • Extra space: O(1); the input is not modified or counted, and there is no recursion stack.

  • Native Python arbitrary-precision shift: for an n-bit integer, time and result space are O(n) because the resulting integer may contain roughly n bits.

  • A shift count of 0 leaves the value unchanged.

  • Negative values require explicit distinction between arithmetic and logical shifts.

  • Python rejects negative shift counts. The function also rejects counts above 31; Java and JavaScript instead apply their language-specific shift-count masking rules.

Common Pitfalls

  • Writing >>> in Python is a syntax error.

  • Assuming >>> converts the variable itself to an unsigned type—it only changes how bits are shifted.

  • Ignoring the operand width: Java distinguishes 32-bit int from 64-bit long.

  • Forgetting to mask with 0xFFFFFFFF when emulating a 32-bit operation in Python.

  • Confusing arithmetic right shift with division: for negative values, >> rounds downward toward negative infinity.

12

How do left and right bit rotations work?

A bit rotation shifts bits in one direction and wraps the bits that leave the word around to the opposite end. Unlike a regular shift, rotation preserves every bit, so it requires a fixed word width such as 8, 16, or 32 bits.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For an unsigned value x stored in width bits, let r be the rotation amount modulo width.

  • Left rotation: Bits move toward the most-significant end; bits shifted out beyond that end wrap into the lowest positions.

  • Right rotation: Bits move toward the least-significant end; bits shifted out beyond that end wrap into the highest positions.

Let mask = (1 << width) - 1, which contains exactly width one-bits. Assuming 0 <= x < 2**width, the formulas are:

  • Left: left_rotate(x, r) = ((x << r) | (x >> (width - r))) & mask

  • Right: right_rotate(x, r) = ((x >> r) | ((x & ((1 << r) - 1)) << (width - r))) & mask

For a right rotation, (1 << r) - 1 isolates the lowest r bits. Only those bits should wrap around to the top; shifting all of x left would incorrectly include additional bits.

Operators and Common Tricks

Python’s bitwise operators operate on individual bits:

  • &: AND, keeps a bit only when both operands have it set.

  • |: OR, sets a bit when either operand has it set.

  • ^: XOR, sets a bit when the operands differ.

  • ~: NOT, inverts every bit. Python integers have arbitrary precision, so ~x == -x - 1; use ~x & mask for a fixed-width complement.

  • <<: Left shift, moves bits toward more-significant positions.

  • >>: Right shift, moves bits toward less-significant positions.

Useful related facts include:

  • x ^ x == 0: XORing a value with itself clears it.

  • x & (x - 1) clears the lowest set bit of a nonzero value.

  • x & -x isolates the lowest set bit of a nonzero value.

  • x > 0 and x & (x - 1) == 0 tests whether x is a power of two.

  • x.bit_count() counts set bits in Python 3.10 and later.

Worked Example

Rotate 10010011 left by two bits in an 8-bit word:

Step Binary
Original 10010011
After one left rotation 00100111
After a second left rotation 01001110

The bit-by-bit movement for the two-bit rotation is:

Destination position 7 6 5 4 3 2 1 0
Source position 5 4 3 2 1 0 7 6
Rotated bit 0 1 0 0 1 1 1 0

The result is 01001110. Rotating the same value right by two bits produces 11100100.

Complexity

  • Fixed width, such as 32 bits: Best, average, and worst-case time are O(1) because only a constant number of bounded machine-word operations are performed.

  • Fixed width: Auxiliary space is O(1). The input is not counted, and no recursion stack is used.

  • Variable-width Python integers: Best, average, and worst-case time are O(width) because Python creates and processes masks and intermediate integers containing up to width bits.

  • Variable-width Python integers: Auxiliary space is O(width) for those intermediate integers. The input is not counted, and no recursion stack is used.

Code Example

def rotate_left(value: int, amount: int, width: int = 32) -> int:
    """Rotate an unsigned value left within a fixed bit width."""
    if width <= 0:
        raise ValueError("width must be positive")
    if value < 0 or value >= (1 << width):
        raise ValueError("value must fit in the specified width")

    amount %= width
    mask = (1 << width) - 1  # Keep exactly the intended width in bits.

    if amount == 0:
        return value

    return ((value << amount) | (value >> (width - amount))) & mask


def rotate_right(value: int, amount: int, width: int = 32) -> int:
    """Rotate an unsigned value right within a fixed bit width."""
    if width <= 0:
        raise ValueError("width must be positive")
    if value < 0 or value >= (1 << width):
        raise ValueError("value must fit in the specified width")

    amount %= width
    mask = (1 << width) - 1  # Keep exactly the intended width in bits.

    if amount == 0:
        return value

    low_bits = value & ((1 << amount) - 1)  # Bits that wrap to the top.
    return ((value >> amount) | (low_bits << (width - amount))) & mask


if __name__ == "__main__":
    print(format(rotate_left(0b10010011, 2, width=8), "08b"))   # 01001110
    print(format(rotate_right(0b10010011, 2, width=8), "08b"))  # 11100100

Common Pitfalls

  • Confusing a rotation with a shift: shifts discard bits and insert zeros; rotations preserve and wrap them.

  • Forgetting to specify the word width. Rotating an 8-bit value differently from a 32-bit value produces different results.

  • Shifting the entire value when implementing a right rotation; extract only the lowest r bits first.

  • Omitting the final mask after a left shift, which can leave extra bits outside the word.

  • A zero rotation amount returns the original value, and an amount larger than the width is safely reduced with % width.

  • Width one is valid and produces the same single-bit value for any rotation amount.

  • Negative values and values that do not fit in the requested width are rejected. Signed two’s-complement rotations require separate semantics.

  • These functions return new integers and do not mutate the input.

13

How do you count set bits in an integer using Python?

A set bit is a binary digit equal to 1. In Python 3.12, int.bit_count() returns the number of set bits in an integer’s magnitude, providing a simple and efficient implementation.

Read full answer

Applies toPython 3.12

How It Works

Python integers have arbitrary precision, so they are not limited to 32 or 64 bits. The bit_count() method examines the integer’s binary representation and counts its 1 bits.

For example:

  • 13 is 1101 in binary and contains three set bits.

  • 0 has no set bits.

  • 1 has one set bit.

  • (-13).bit_count() also returns 3 because the method counts the bits in the integer’s absolute value.

An alternative interview algorithm is Brian Kernighan’s algorithm. For a nonnegative integer, repeatedly applying value &= value - 1 clears the lowest set bit, so the number of iterations equals the number of set bits.

Bitwise Operators

Operator Purpose Example
& Bitwise AND 1100 & 1010 = 1000
| Bitwise OR 1100 | 1010 = 1110
^ Bitwise XOR 1100 ^ 1010 = 0110
~ Bitwise complement ~5 == -6 because ~x == -x - 1
<< Shift bits left 5 << 1 == 10
>> Shift bits right 5 >> 1 == 2

Use format(value, "08b") to display binary digits. For example, format(5, "08b") returns "00000101".

The AND operation works bit by bit:

Bit position 1100 1010 1100 & 1010
3 1 1 1
2 1 0 0
1 0 1 0
0 0 0 0

Other useful bit tricks include:

  • x & (x - 1): For nonnegative x, clears its lowest set bit. Subtracting one changes that bit to zero and the lower zero bits to ones, which the AND removes.

  • x & -x: For positive x, isolates its lowest set bit because -x represents the two’s-complement form of x in Python.

  • x ^ x == 0: XOR compares identical bits and produces zero, so XORing a number with itself yields zero.

  • x > 0 and (x & (x - 1)) == 0: Checks whether x is a power of two because such a number has exactly one set bit, which becomes zero after the operation.

Example Walkthrough

Using Kernighan’s algorithm with 13:

Step Binary value Operation
1 1101 13 & 12 = 1100
2 1100 12 & 11 = 1000
3 1000 8 & 7 = 0000
4 0000 Loop ends after three iterations

Therefore, 13 contains three set bits.

Complexity

Let N be the bit length of the integer’s magnitude.

  • Fixed-width integers: Best, average, and worst time are O(1) because the width is constant.

  • Arbitrary-precision integers: Best time is O(1) for zero; average and worst time are O(N) because bit_count() scans the integer’s internal digits.

  • Auxiliary space: O(1) machine words, excluding the input integer and returned count. There is no recursion stack. The input itself occupies O(N) bits.

  • Manual Kernighan algorithm: It performs O(k) iterations, where k is the number of set bits. This is O(k) time and O(1) auxiliary space for fixed-width integers. With arbitrary-precision Python integers, each update can cost O(N), giving O(kN) worst-case time and O(N) bits of auxiliary space for temporary integers.

Code Example

def count_set_bits(value: int) -> int:
    """Return the number of 1 bits in the integer's magnitude."""
    return value.bit_count()


result = count_set_bits(13)
print(result)  # 3

Common Pitfalls

  • Negative integers: bit_count() counts the absolute value, not an infinite two’s-complement representation. Use abs(value) before a manual magnitude-based algorithm.

  • Fixed-width behavior: To count set bits in a signed 32-bit two’s-complement value, mask it first with value & 0xFFFFFFFF, then call bit_count().

  • Overflow: Python integers do not overflow; fixed-width overflow only matters when translating the algorithm to languages such as C++ or Java.

  • Zero: A manual loop using while value: naturally stops immediately and returns 0; no special branch is required.

  • Common follow-up: Interviewers may ask for a manual x & (x - 1) solution, a 32-bit version, or the time and space complexity of both approaches.

14

How to check if a number is a power of two using bits

A positive integer is a power of two if its binary representation contains exactly one set bit. The standard bit-manipulation test is number > 0 and (number & (number - 1)) == 0.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For a power of two such as 8:

  • 8 is binary 1000.

  • 8 - 1 is binary 0111.

  • Their bitwise AND is 0000.

Subtracting one from a positive integer clears its lowest set bit and changes all lower zero bits to ones. Therefore:

  • A power of two has one set bit, so number & (number - 1) becomes zero.

  • A number with multiple set bits retains its other set bits after the operation, producing a nonzero result.

  • The number > 0 check excludes zero, which otherwise passes the bitwise test.

Bit-by-bit example:

Bit position 8 (1000) 7 (0111) AND result
3 1 0 0
2 0 1 0
1 0 1 0
0 0 1 0

Bitwise Operator Reference

Using format(10, "04b") → 1010 and format(12, "04b") → 1100:

Operator Meaning Example
& Bitwise AND 1010 & 1100 → 1000
| Bitwise OR 1010 | 1100 → 1110
^ Bitwise XOR 1010 ^ 1100 → 0110
~ Bitwise NOT In Python, ~x == -x - 1
<< Shift bits left 1010 << 1 → 10100
>> Shift bits right 1010 >> 1 → 0101

Python integers have arbitrary precision, so shifting does not overflow. To model unsigned 32-bit results, mask each value with 0xFFFFFFFF. To interpret the masked value as signed two’s complement, convert an unsigned value u to u if u < 0x80000000 else u - 0x100000000.

Approaches and Complexity

Let k be the number of bits in the input.

Approach Time Auxiliary space When to use
Repeated division by two O(k) iterations; O(k²) total bit time in Python because each division can process O(k) bits O(k) temporary bits Primarily for demonstrating the basic mathematical property
x & (x - 1) O(k) bit time because subtraction and AND each process the arbitrary-precision integer O(k) temporary bits Recommended bit-manipulation solution
x & (x - 1) for fixed-width integers O(1) because subtraction and AND are constant-width operations O(1) Standard 32-bit or 64-bit interview model

For the Python bit trick, best, average, and worst-case time are all O(k). The auxiliary-space figures exclude the input itself and include temporary integers; there is no recursion stack.

In interviews with bounded machine integers, it is conventional to report O(1) time and O(1) auxiliary space for this operation because only a fixed number of constant-width operations are required.

Code Example

def is_power_of_two(number: int) -> bool:
    """Return whether number is a positive integer power of two."""
    return number > 0 and (number & (number - 1)) == 0


number = 16
print(f"{number:08b}")          # 00010000
print(f"{number - 1:08b}")      # 00001111
print(is_power_of_two(number))  # True

Common Pitfalls

  • Forgetting zero: 0 is not a power of two. The positivity check is required.

  • Excluding one accidentally: 1 is 2⁰, so the function correctly returns True.

  • Rejecting negatives: Negative integers are not powers of two.

  • Ignoring integer width: The trick is O(1) for fixed-width integers but O(k) with Python’s arbitrary-precision integers.

  • Using subtraction without checking zero: In Python, 0 & -1 is zero, which demonstrates why number > 0 must come first.

  • Confusing XOR with AND: XORing a number with itself produces zero because x ^ x == 0; it does not test whether x has one set bit.

A common follow-up asks how to count set bits. In Python 3.10 and later, use number.bit_count().

15

Add two integers using bitwise operations in Python 3.12

A bitwise adder computes binary addition using XOR for the provisional sum and AND with a left shift for carry propagation. This Python 3.12 implementation handles positive numbers, negative numbers, and zero without using the + operator.

Read full answer

Applies toPython 3.12

How It Works

For each binary position:

  • left ^ right gives the provisional sum bit when there is no incoming carry.

  • left & right identifies positions that generate a carry.

  • Shifting that carry left moves it to the next binary position.

  • Repeating the process until the carry becomes zero completes the addition.

format(5, "08b") produces 00000101, while format(3, "08b") produces 00000011.

Left Right XOR result AND result Shifted carry
00000101 00000011 00000110 00000001 00000010
00000110 00000010 00000100 00000010 00000100
00000100 00000100 00000000 00000100 00001000
00000000 00001000 00001000 00000000 00000000

The final result is 00001000, which is 8.

Bitwise Operators

Operator Meaning Python example
& Bitwise AND 0b0101 & 0b0011 gives 0b0001
| Bitwise OR 0b0101 | 0b0011 gives 0b0111
^ Bitwise XOR 0b0101 ^ 0b0011 gives 0b0110
~ Bitwise NOT ~x == -x - 1; ~0b0101 == -0b0110
<< Left shift 0b0001 << 2 gives 0b0100
>> Right shift 0b0100 >> 2 gives 0b0001

For a negative Python integer, >> is an arithmetic right shift, equivalent to floor division by a power of two. Python integers have arbitrary precision and therefore do not overflow.

Handling Negative Numbers

The function converts each operand to fixed-width two’s complement:

  • A negative magnitude is inverted with ~ and masked.

  • One is added to the inverted magnitude using the same carry procedure.

  • The operands are added modulo the selected width.

  • The sign bit determines whether the masked result represents a positive or negative number.

Code Example

def add_without_plus(first: int, second: int) -> int:
    """Add two integers using bitwise operations only."""
    if not isinstance(first, int) or not isinstance(second, int):
        raise TypeError("Both arguments must be integers")

    def add_magnitudes(left: int, right: int) -> int:
        """Add two non-negative integers using XOR and carry propagation."""
        while right:
            carry = left & right
            left = left ^ right
            right = carry << 1
        return left

    def increment(value: int) -> int:
        """Return value increased by one using bitwise addition."""
        return add_magnitudes(value, 1)

    max_bits = max(first.bit_length(), second.bit_length())

    # Reserve enough width for the operands, result magnitude, and sign bit.
    width = max(increment(increment(max_bits)), 2)
    mask = (1 << width) - 1
    modulus = 1 << width
    sign_bit = 1 << (width - 1)

    def to_twos_complement(value: int) -> int:
        """Encode an integer as a fixed-width two's-complement value."""
        if value >= 0:
            return value & mask

        inverted = ~(-value) & mask
        return add_magnitudes(inverted, 1)

    encoded_sum = (
        add_magnitudes(
            to_twos_complement(first),
            to_twos_complement(second),
        )
        & mask
    )

    if encoded_sum & sign_bit:
        return encoded_sum - modulus

    return encoded_sum


print(add_without_plus(5, 3))       # 8
print(add_without_plus(-7, 5))      # -2
print(add_without_plus(0, 0))       # 0
print(add_without_plus(5, 5))       # 10

Complexity

Let b be the maximum bit length of the operands, excluding their signs.

  • Carry rounds: best O(1), average expected O(log b), and worst O(b). A carry can propagate across at most b positions; for uniformly random bit patterns, the expected longest carry chain is O(log b).

  • Fixed-width machine-word model: O(1) total time because the word width and therefore the maximum number of rounds are fixed.

  • Python arbitrary-precision model: best O(b), average expected O(b log b), and worst O(b²) bit operations. Each round performs operations on O(b)-bit integers, and there can be O(b) rounds.

  • Auxiliary space: O(1) machine words in the fixed-width model, or O(b) bits for Python’s temporary integers. The inputs are not counted, and the call-stack depth is constant because the implementation is not recursive.

Common Pitfalls

  • Using left ^ right without propagating left & right produces XOR, not addition.

  • Forgetting that Python’s ~x equals -x - 1.

  • Failing to mask two’s-complement values before checking the sign bit.

  • Assuming the simple carry algorithm handles negative operands without conversion.

  • Choosing a width too small to represent the result and its sign.

  • Expecting Python integer overflow; Python integers are arbitrary precision.

  • Empty or one-element collections, sortedness, graph connectivity, and cycles are not applicable because this function accepts exactly two integers. Equal operands are valid and are handled by the same algorithm.

16

How do you swap two variable values without using extra space?

Use the XOR swap trick, which exchanges two integer values using three XOR operations and no temporary integer variable. In Python, integers are immutable, so a function returns the swapped values for the caller to assign back.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How XOR Swap Works

XOR has these useful properties:

  • x ^ x = 0

  • x ^ 0 = x

  • XOR is associative and commutative.

Given left and right:

  1. left ^= right makes left contain left ^ right.

  2. right ^= left makes right contain the original left.

  3. left ^= right makes left contain the original right.

For example, swapping 10 (1010) and 5 (0101):

Step left right Binary left Binary right
Initial 10 5 1010 0101
left ^= right 15 5 1111 0101
right ^= left 15 10 1111 1010
left ^= right 5 10 0101 1010

Essential Bitwise Operators

For 5 (00000101) and 3 (00000011), the XOR 5 ^ 3 produces 00000110 (6) bit by bit:

Bit position 7 6 5 4 3 2 1 0
5 0 0 0 0 0 1 0 1
3 0 0 0 0 0 0 1 1
5 ^ 3 0 0 0 0 0 1 1 0
Operator Meaning Example Result
& Bitwise AND 5 & 3 1 (00000001)
| Bitwise OR 5 | 3 7 (00000111)
^ Bitwise XOR 5 ^ 3 6 (00000110)
~ Bitwise NOT ~5 -6
<< Left shift 5 << 1 10 (00001010)
>> Right shift 10 >> 1 5 (00000101)

Python integers use arbitrary precision. Their bitwise operations behave as if negative integers had infinitely many two’s-complement sign bits, so ~x equals -x - 1, and integer operations do not overflow.

Code Example

def swap_without_temp(left: int, right: int) -> tuple[int, int]:
    """Swap two integers using XOR without a temporary integer."""
    left ^= right
    right ^= left
    left ^= right
    return left, right


left, right = 10, 5
print(format(left, "08b"), format(right, "08b"))
# Output: 00001010 00000101

left, right = swap_without_temp(left, right)
print(left, right)
# Output: 5 10

Complexity

For fixed-width integers:

  • Best, average, and worst-case time: O(1) — the algorithm performs exactly three XOR operations.

  • Auxiliary space: O(1) — it introduces no third temporary integer variable, and the input values are not counted.

For Python arbitrary-precision integers containing at most k bits:

  • Best, average, and worst-case time: O(k) — each XOR processes the operands’ bit representations.

  • Auxiliary space: O(k) — Python allocates new immutable integer results even though the algorithm uses no separate temporary variable. The input values are not counted.

The returned tuple is the function’s output and is excluded from auxiliary-space analysis.

Common Pitfalls

  • Python immutability: left ^= right rebinds the local name to a new integer; it does not mutate the caller’s integer. Assign the returned tuple back with left, right = swap_without_temp(left, right).

  • Non-integer values: XOR is defined here for integers. Use Python’s left, right = right, left for generic values.

  • Equal values: Swapping two equal integers safely leaves both unchanged.

  • Zero and negative values: The XOR identities still work, including with Python’s arbitrary-precision representation.

  • Strict space interpretation: The trick removes a third temporary variable, but Python still allocates intermediate integer objects.

17

How do I find the single non-repeating element using XOR?

XOR identifies the unique element because x ^ x = 0, while 0 ^ x = x. XORing every array element therefore cancels all values that occur twice and leaves only the non-repeating value.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why XOR Works

The bitwise XOR operator has three useful properties:

  • x ^ x = 0: identical values cancel.

  • 0 ^ x = x: XOR with zero preserves a value.

  • XOR is associative and commutative, so element order does not matter.

Consequently, for an array containing one value once and every other value exactly twice:

(a ^ a) ^ (b ^ b) ^ ... ^ unique = 0 ^ ... ^ unique = unique

This works even when the array is already sorted, because the algorithm does not depend on ordering.

Bitwise Operators

Operator Name Behavior
x & y Bitwise AND Produces a set bit only when both corresponding bits are 1.
x | y Bitwise OR Produces a set bit when either corresponding bits are 1.
x ^ y Bitwise XOR Produces a set bit when the corresponding bits differ.
~x Bitwise NOT Inverts every bit. In Python, ~x == -x - 1.
x << k Left shift Moves the bits of x left by k positions.
x >> k Right shift Moves the bits of x right by k positions.

For example, format(5, "08b") produces "0101" and format(3, "08b") produces "0011".

Bit position 5 3 5 ^ 3
3 0 0 0
2 1 0 1
1 0 1 1
0 1 1 0

Thus, 5 ^ 3 is 0110, which is 6.

Worked Example

For the array [1, 2, 1, 3, 2, 3, 7]:

Processed value Accumulator
Initial 0
1 1
2 3
1 2
3 1
2 3
3 0
7 7

Every duplicated value cancels, leaving 7.

Code Example

def find_single_non_repeating(values: list[int]) -> int:
    """Return the only value that occurs once while all others occur twice."""
    if not values:
        raise ValueError("The array must contain at least one element")

    result = 0
    for value in values:
        result ^= value

    return result


print(find_single_non_repeating([1, 2, 1, 3, 2, 3, 7]))  # 7

The function does not modify the input and requires no sorting, dictionary, or additional collection.

Complexity and Edge Cases

  • Best case: O(n), because every element must be examined.

  • Average case: O(n), since each element is processed once.

  • Worst case: O(n), including when the unique element is first or last.

  • Auxiliary space: O(1) for fixed-width integers, excluding the input; there is no recursion stack. If the input is counted, total space is O(n).

Python integers have arbitrary precision. If B is the maximum bit length of any input integer, each XOR takes up to O(B) bit operations, so the total time is O(nB) and the accumulator requires O(B) auxiliary bits. Counting the input gives O(nB) bits in the worst case. For machine-sized integers, these bounds reduce to the customary O(n) time and O(1) auxiliary space.

Important edge cases:

  • Empty input: The implementation raises ValueError because no unique element exists.

  • One element: The function returns that element.

  • Negative numbers: XOR works correctly with Python’s signed integers.

  • Already sorted input: Results are unchanged.

  • Python overflow: Python integers do not overflow.

Common Pitfalls

  • ^ is XOR in Python; exponentiation uses **.

  • The algorithm depends on parity. A value occurring three times behaves as if it occurred once, so malformed input can produce an unexpected result.

  • With multiple non-repeating values, XOR returns their combined XOR rather than identifying either one.

  • The empty array has no answer and must be handled explicitly.

  • A common follow-up asks for one unique element when every other element occurs three times. The same XOR approach still works because x ^ x ^ x = x.

18

Find the unique number when all others appear three times?

Bitmask state tracking finds the non-repeated number by maintaining two masks that record how many times each bit has appeared modulo 3. Numbers occurring three times contribute zero to the final masks, leaving only the unique number.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For each integer number, maintain two bitmasks:

  • ones contains bits whose occurrence count is 1 modulo 3.

  • twos contains bits whose occurrence count is 2 modulo 3.

Update them with:

ones = (ones ^ number) & ~twos
twos = (twos ^ number) & ~ones

For every bit, the state (ones, twos) moves through three states:

Previous state Input bit 0 Input bit 1
00: seen zero times 00 10
10: seen once 10 01
01: seen twice 01 00

After the third occurrence, the bit returns to 00. Therefore, values appearing exactly three times cancel out, while the unique value remains in ones.

Bitwise Toolkit

  • & — AND: A result bit is 1 only when both input bits are 1.

  • | — OR: A result bit is 1 when either input bit is 1.

  • ^ — XOR: A result bit is 1 when the input bits differ.

  • ~ — NOT: In Python, ~x equals -x - 1, such as ~12 == -13.

  • << — left shift: x << k multiplies x by 2^k.

  • >> — right shift: x >> k divides by 2^k, using floor division for negative values.

Python’s format(value, "08b") displays an eight-bit binary representation. For example, 12 and 10 produce:

Bits 7 6 5 4 3 2 1 0
12 0 0 0 0 1 1 0 0
10 0 0 0 0 1 0 1 0
12 & 10 0 0 0 0 1 0 0 0
12 | 10 0 0 0 0 1 1 1 0
12 ^ 10 0 0 0 0 0 1 1 0

Python integers have arbitrary precision and do not overflow. The algorithm consequently works with negative integers as well as positive ones.

Example Walkthrough

For [1, 1, 1, 2, 2, 2, 3]:

Processed value ones twos
Initial 0 0
1 1 0
1 0 1
1 0 0
2 2 0
2 0 2
2 0 0
3 3 0

The final mask is 3, or 00000011 in binary.

Code Example

def find_single_non_repeated(numbers: list[int]) -> int:
    """Return the unique integer when every other integer occurs three times."""
    if not numbers:
        raise ValueError("The input must contain exactly one non-repeated number.")

    ones = 0
    twos = 0

    for number in numbers:
        ones = (ones ^ number) & ~twos
        twos = (twos ^ number) & ~ones

    return ones


print(find_single_non_repeated([1, 1, 1, 2, 2, 2, 3]))  # 3

Complexity and Edge Cases

  • Best, average and worst-case time: O(n) under the fixed-width word model because every number is processed once using a constant number of bitwise operations.

  • Arbitrary-precision time: O(nB) bit operations when each integer has at most B bits, because Python operations on B-bit integers cost O(B).

  • Auxiliary space: O(1) machine words for the two masks, excluding the input list. In a bit-level model, the masks require O(B) space.

  • An empty list raises ValueError; a one-element list returns that element.

  • Zero, negative values and repeated values are handled naturally.

  • The function assumes every non-unique value occurs exactly three times.

Common Pitfalls

  • Update order matters: Update ones before twos, because the second expression uses the newly updated ones.

  • XOR alone is insufficient: x ^ x cancels two occurrences; it does not directly cancel three.

  • Avoid fixed-width assumptions: Python has arbitrary-precision integers. If a problem explicitly requires signed 32-bit behavior, use & 0xFFFFFFFF when operating on unsigned 32-bit representations.

  • Interview follow-ups: A common variation asks for the unique number when all others occur twice; that problem uses a simpler XOR-based solution. Another variation allows arbitrary occurrence counts, where a dict with O(n) time and O(k) space is more appropriate.

19

How can you isolate and unset the least significant set bit?

The lowest set bit is the rightmost 1 in a number’s binary representation. Isolate it with x & -x, then clear that position with x & (x - 1); when x == 0, no set bit exists.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Isolating the lowest set bit: x & -x produces a power of two containing only the rightmost set bit.

  • For x = 12 (1100), x & -x is 0100, so the lowest set bit has value 4.

  • Clearing the lowest set bit: x & (x - 1) removes the rightmost 1.

  • Subtracting one changes that 1 to 0, while all lower bits become 1. ANDing with the original number therefore clears only the selected bit.

  • Zero case: There is no lowest set bit in 0, so the implementation returns (0, 0).

  • Negative numbers: Python represents negative integers using infinite two’s complement, and both identities remain valid. For example, clearing the lowest set bit of -12 produces -16.

Related bit-manipulation idioms include:

  • x ^ x == 0 because identical bits cancel.

  • x > 0 and x & (x - 1) == 0 tests whether a positive integer is a power of two.

  • x.bit_count() counts set bits in Python 3.10 and later.

  • x & 0xFFFFFFFF obtains the unsigned 32-bit two’s-complement pattern of x when fixed-width behavior is required.

Bitwise Operators

Operator Name Behavior
& AND Keeps a bit as 1 only when both corresponding bits are 1.
| OR Sets a bit to 1 when either corresponding bit is 1.
^ XOR Sets a bit to 1 when the corresponding bits differ.
~ NOT Inverts every bit; in Python, ~x == -x - 1.
<< Left shift Shifts bits left, multiplying a nonnegative integer by a power of two.
>> Right shift Shifts bits right, dividing a nonnegative integer by a power of two with rounding down.

Python integers have arbitrary precision, so they do not overflow. The identity ~x == -x - 1 follows from Python’s infinite two’s-complement representation.

Example Walkthrough

For x = 12:

Operation Binary result Decimal result
x 1100 12
x - 1 1011 11
x & (x - 1) 1000 8
x & -x 0100 4

In an 8-bit two’s-complement view, -12 is 11110100. ANDing it with 1100 produces 0100, isolating bit value 4.

Complexity

Let k be the number of bits in the input’s magnitude.

  • Best time: O(k) — Python creates and processes arbitrary-precision intermediate integers.

  • Average time: O(k) — the operations consistently depend on the integer’s storage size.

  • Worst time: O(k) — negation, subtraction and bitwise operations may process all k bits.

  • Auxiliary space: O(k) bits — temporary integers such as -x and x - 1 require proportional storage. The input itself is not counted.

For fixed-width machine integers such as 32-bit or 64-bit values, the corresponding time and auxiliary-space complexities are both O(1).

Code Example

def find_and_clear_lowest_set_bit(number: int) -> tuple[int, int]:
    """Return (cleared_number, lowest_set_bit), or (0, 0) for zero."""
    if number == 0:
        return 0, 0

    lowest_set_bit = number & -number       # Isolate the rightmost 1
    cleared_number = number & (number - 1)  # Clear the rightmost 1
    return cleared_number, lowest_set_bit


print(format(12, "08b"))                     # 00001100
print(find_and_clear_lowest_set_bit(12))      # (8, 4)
print(find_and_clear_lowest_set_bit(0))       # (0, 0)
print(find_and_clear_lowest_set_bit(-12))     # (-16, 4)

Common Pitfalls

  • Zero input: 0 has no set bit, so a separate sentinel or None is needed if the result type permits it.

  • Bit indexing: Set-bit positions are normally zero-based; the rightmost bit has index 0.

  • Fixed-width assumptions: Python does not overflow, unlike many 32-bit or 64-bit languages. Mask explicitly when reproducing fixed-width two’s-complement behavior.

  • Mutation: Python integers are immutable, so the original value is never changed.

  • Ambiguous return value: If the interview expects only the cleared number, return x & (x - 1) rather than the tuple.

  • Edge cases: The input is one scalar integer, so empty-collection, duplicate-element, sorting and graph-related edge cases do not apply.

20

How do you generate the next integer with the same set-bit count?

The Gosper’s hack, also called the Snoob transformation, finds the smallest integer greater than a given number that has exactly the same number of set bits. It performs the operation using a few bitwise operations without scanning every bit.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm works by treating the set bits as a binary permutation:

  1. number & -number isolates the rightmost set bit.

  2. Adding that bit to the number creates a carry through the lowest contiguous run of 1 bits.

  3. The changed positions are identified with XOR.

  4. The remaining bits are shifted into their lowest possible positions.

  5. The carried result and restored bits are combined with OR.

The result is the next number with the same population count, rather than just any larger number with that count.

Bitwise Operators and Tricks

Python integers are arbitrary precision, so these operations do not overflow.

  • AND (&): keeps only bits present in both operands.

  • OR (|): sets a bit when it appears in either operand.

  • XOR (^): sets a bit when the operands differ.

  • NOT (~): in Python, ~x == -x - 1, because Python uses an infinite-width two’s-complement representation.

  • Left shift (<<): moves bits left, multiplying by two per position.

  • Right shift (>>): moves bits right, dividing by two per position.

For example:

format(0b1010, "08b")  # "00001010"
format(0b0110, "08b")  # "00000110"

0b1010 & 0b0110  # 00000010
0b1010 | 0b0110  # 00001110
0b1010 ^ 0b0110  # 00001100
~0b1010          # -11
0b1010 << 1      # 00010100
0b1010 >> 1      # 00000101

For a fixed 8-bit unsigned interpretation, mask the result with 0xFF. For example, format((~0b1010) & 0xFF, "08b") is "11110101".

Useful related tricks include:

  • x & (x - 1) clears the rightmost set bit.

  • x & -x isolates the rightmost set bit.

  • x ^ x produces zero for a single number.

  • x.bit_count() counts the set bits in Python 3.10 and later.

Worked Example

For number = 10, whose binary representation is 1010:

Bit position 3 2 1 0
number 1 0 1 0
lowest_set_bit 0 0 1 0
ripple = number + lowest_set_bit 1 1 0 0
changed = number ^ ripple 0 1 1 0
restored 0 0 0 0
Result 1 1 0 0

The result is 12, or 1100. Both 10 and 12 have two set bits, and no integer between them has two set bits.

Code Example

def next_higher_same_popcount(number: int) -> int:
    """Return the smallest integer greater than number with equal set-bit count."""
    if number <= 0:
        raise ValueError("number must be positive")

    lowest_set_bit = number & -number
    ripple = number + lowest_set_bit
    changed = number ^ ripple

    # Equivalent to: (changed >> 2) // lowest_set_bit
    restored = changed >> (lowest_set_bit.bit_length() + 1)

    return ripple | restored


print(next_higher_same_popcount(10))  # 12

Complexity and Edge Cases

Let b be the number of bits in the input integer.

  • Time: best, average, and worst case are O(b) for Python’s arbitrary-precision integers because the arithmetic and bitwise operations process the integer’s words. For a fixed machine-width integer, this is O(1).

  • Auxiliary space: O(b) bits for intermediate integers. The input and returned result are not counted; the recursion stack is O(1) because the implementation is iterative.

  • Positive input: required by the question; non-positive values raise ValueError.

  • One-bit inputs: for example, 1 becomes 2.

  • Duplicate bit patterns: duplicates are irrelevant because the result is determined by the integer’s binary representation.

  • Unbounded width: Python can return a result requiring more bits than the input. If a fixed-width result is required, an overflow check must be added separately.

Common Pitfalls

  • Do not assume the answer is simply number + 1; the added one may change the population count.

  • Remember that ~x is -x - 1 in Python, not a finite-width bitwise complement by itself.

  • Do not use x & (x - 1) when the goal is to isolate the lowest set bit; use x & -x.

  • In languages with fixed-width integers, watch for overflow. Python avoids this automatically.

  • If the result must remain within a specified bit width, explicitly verify that the computed value fits.

21

How do you reverse the bits of an unsigned integer?

Bit reversal rearranges a fixed-width unsigned integer so its least significant bit becomes the most significant bit and vice versa. The width must be specified—typically 32 bits—because leading zero bits determine the result.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The standard approach repeatedly:

  1. Extracts the least significant bit using value & 1.

  2. Shifts the result left with reversed_value << 1.

  3. Adds the extracted bit using |.

  4. Removes the processed bit from the input using value >>= 1.

  5. Repeats exactly once for every bit in the specified width.

For example, reversing the 8-bit value 0b00000010 produces 0b01000000, which is 64.

Bitwise Operators and Common Tricks

Operator Purpose Example
& Bitwise AND; extracts or checks selected bits 0b1000 & 0b1100 → 0b1000
| Bitwise OR; combines or sets selected bits 0b1000 | 0b0100 → 0b1100
^ Bitwise XOR; toggles differing bits 0b1000 ^ 0b0100 → 0b1100
~ Bitwise NOT; in Python, ~x == -x - 1 ~0b00001000 → -9
<< Shifts bits left, multiplying by two per position 0b00001000 << 1 → 0b00010000
>> Shifts bits right; logical for Python’s non-negative integers 0b00001000 >> 1 → 0b00000100

For binary formatting, format(0b00001000, "08b") returns "00001000".

Useful related tricks include:

  • x & (x - 1): clears the lowest set bit.

  • x & -x: isolates the lowest set bit when x > 0.

  • x ^ x: equals zero because identical bits cancel.

  • x > 0 and x & (x - 1) == 0: tests whether x is a power of two.

  • x.bit_count(): counts set bits in Python 3.10 and later.

Complexity

For a width of w bits:

  • Time: best, average and worst case are O(w) because the loop processes every bit once. With a fixed 32-bit width, this is O(1) because exactly 32 iterations occur.

  • Space: O(1) auxiliary space for fixed-width integers, excluding the input and output. There is no recursion stack. If arbitrary-width Python integers are allowed, the accumulator requires O(w) bits.

Code Example

def reverse_bits(value: int, width: int = 32) -> int:
    """Reverse the lowest `width` bits of a non-negative integer."""
    if width <= 0:
        raise ValueError("width must be positive")
    if value < 0 or value.bit_length() > width:
        raise ValueError("value must be non-negative and fit in width bits")

    reversed_value = 0

    for _ in range(width):
        reversed_value = (reversed_value << 1) | (value & 1)
        value >>= 1

    return reversed_value


print(reverse_bits(0b00000010, width=8))  # 64 (0b01000000)

Example Walkthrough

For value = 0b00000010 and width = 8:

Iteration Value Before Extracted Bit Accumulator After
1 00000010 0 00000000
2 00000001 1 00000001
3 00000000 0 00000010
4 00000000 0 00000100
5 00000000 0 00001000
6 00000000 0 00010000
7 00000000 0 00100000
8 00000000 0 01000000

The final result is 0b01000000, or 64.

Common Pitfalls

  • Choosing the wrong width: reverse_bits(1, 8) returns 128 (2^7), while the 32-bit version returns 2147483648 (2^31).

  • Ignoring leading zeros: String-based reversal can lose the fixed-width padding unless it is padded explicitly.

  • Using ~ as an unsigned complement: Python returns -x - 1; use (~x) & 0xFFFFFFFF for a 32-bit complement.

  • Confusing arithmetic and logical shifts: Right-shifting a negative signed integer is implementation-dependent in many languages, but the implementation above rejects negative inputs.

  • Ignoring integer limits: Python integers do not overflow, but implementations using fixed-width types should use an explicitly unsigned type.

  • Edge cases: 0 reverses to 0, an all-zero value remains zero, and 2^w - 1 reverses to itself.

Common interview follow-ups include adapting the algorithm to 8-, 16-, or 64-bit widths, counting set bits, computing Hamming distance, and clarifying that bit reversal is independent of byte endianness.

22

How do you calculate an integer’s absolute value with bit manipulation?

Bit manipulation computes an integer’s absolute value by creating an all-zero or all-one mask and applying XOR and subtraction. In Python, this works without fixed-width overflow because integers have arbitrary precision.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The formula is:

absolute_value = (value ^ mask) - mask

The mask determines the sign:

  • Nonnegative value: The mask is 0, so XOR leaves the value unchanged and subtracting 0 has no effect.

  • Negative value: The mask is -1, whose binary representation acts as all ones. XOR with -1 complements every bit, and subtracting -1 effectively adds one: ~value + 1 = -value.

In Python, the mask can be generated without a comparison:

mask = value >> value.bit_length()

For a nonnegative number, shifting right by its bit length produces 0. For a negative number, Python’s arithmetic right shift produces -1. For zero, 0 >> 0 also produces 0.

Bitwise Operator Reference

Using 12 and 10:

format(12, "08b")  # 00001100
format(10, "08b")  # 00001010
Operator Name Example Result Purpose
& Bitwise AND 12 & 10 8 Keeps bits set in both operands
| Bitwise OR 12 | 10 14 Sets bits present in either operand
^ Bitwise XOR 12 ^ 10 6 Sets bits present in exactly one operand
~ Bitwise NOT ~12 -13 Inverts bits; in Python, ~x == -x - 1
<< Left shift 12 << 1 24 Multiplies by two for each shifted bit
>> Right shift 12 >> 1 6 Divides by two, rounding down

Bit-by-Bit Example

For -12, using an 8-bit two’s-complement illustration:

Stage Binary
value 11110100
mask 11111111
value ^ mask 00001011
(value ^ mask) - mask 00001100

The final value is 12. Python does not restrict integers to 8 bits, but the same bit logic applies.

Complexity

Let k be the number of bits in the integer.

  • Best, average, and worst-case time: O(k) for Python’s arbitrary-precision operations; conceptually O(1) for fixed-width integers because only a constant number of operations is performed.

  • Auxiliary space: O(k) in Python for temporary arbitrary-precision integers; O(1) for fixed-width integers. The input is not counted, and there is no recursion stack.

Code Example

def absolute_value(value: int) -> int:
    """Return the absolute value of an integer using bitwise operations."""
    mask = value >> value.bit_length()
    return (value ^ mask) - mask


print(absolute_value(-12))  # Expected output: 12

Common Pitfalls

  • Confusing ~x with -x: In Python, ~x equals -x - 1; the formula deliberately compensates for that behavior.

  • Ignoring Python’s arbitrary precision: Python has no integer overflow, so the absolute value of a very large negative integer remains correct.

  • Applying fixed-width assumptions: In a signed 32-bit environment, the most-negative value has no representable positive counterpart. Python does not have this limitation.

  • Using the formula in other languages unchanged: Confirm the language’s signed right-shift behavior. The explicit conditional mask, 0 for nonnegative values and -1 for negative values, is more portable.

  • Edge cases: Zero returns 0, positive values remain unchanged, and negative values become their positive magnitude.

  • Production code: Prefer Python’s built-in abs() in ordinary application code; use the bitwise version to demonstrate understanding of representation and mask-based arithmetic.

23

How do bit shifts multiply and divide a number by two?

Bit shifting moves a binary integer left or right: x << 1 doubles it, while Python’s arithmetic right shift x >> 1 computes x // 2.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Left shift (x << 1): Moves every binary digit one position left. Each bit gains a value twice as large, so the mathematical result is the original number multiplied by two.

  • Right shift (x >> 1): Moves every binary digit one position right and discards the least significant bit. In Python, this is equivalent to floor division by two, including for negative numbers.

  • A left shift only repositions bits; a right shift also removes one bit. For a general shift count k, the mathematical effects are multiplication or division by 2**k.

Signed right-shift behavior can vary by language and type: Python uses an arithmetic right shift, while logical right shifts such as JavaScript’s >>> do not preserve the sign.

Bitwise Operator Reference

Operator Bit-level behaviour Example
x & y AND: a result bit is 1 only when both input bits are 1 5 & 3 is 1
x | y OR: a result bit is 1 when either input bit is 1 5 | 3 is 7
x ^ y XOR: a result bit is 1 when the input bits differ 5 ^ 3 is 6
~x NOT: flips every bit ~5 is -6 in Python
x << k Shift left by k positions 5 << 1 is 10
x >> k Shift right by k positions 5 >> 1 is 2

Python integers have arbitrary precision, so ~x equals -x - 1, and integer overflow does not occur.

Worked Bit Example

Starting with 21, whose eight-bit binary representation is 00010101:

Step Binary Decimal Reason
Original 00010101 21 Starting value
Shift left 00101010 42 Each bit moves one column left
Shift right 00001010 10 The rightmost bit is discarded

This demonstrates why shifting can double or halve a value without ordinary multiplication or division.

Code Example

def multiply_and_divide_by_two(value: int) -> tuple[int, int]:
    """Return value multiplied by two and floor-divided by two."""
    doubled = value << 1
    halved = value >> 1
    return doubled, halved


print(multiply_and_divide_by_two(21))  # (42, 10)
print(format(21, "08b"))           # 00010101
print(format(21 << 1, "08b"))       # 00101010
print(format(21 >> 1, "08b"))       # 00001010

For negative values, -5 >> 1 is -3. This matches Python’s floor division, -5 // 2 == -3, rather than rounding toward zero.

Complexity and Edge Cases

  • Fixed-width integers: Both operations take O(1) time and O(1) space, including the returned result, because the number of bits is constant. The input is not counted.

  • Python arbitrary-precision integers: For an input containing b bits, shifting takes O(b) time and O(b) output space because Python allocates and copies an integer containing up to b + 1 bits. The input is not counted.

  • Zero: Both operations return 0.

  • Negative numbers: Python’s >> 1 rounds downward; use an explicit rounding rule if truncation toward zero is required.

  • Large integers: Python does not overflow. For a nonzero integer, shifting left increases the binary length of its magnitude by exactly one bit.

Common Pitfalls

  • Confusing shifts with arithmetic operators: In Python, x << 1 is equivalent to x * 2, while x >> 1 is equivalent to x // 2, not the float-producing x / 2.

  • Ignoring negative-number rounding: Python’s right shift of -5 produces -3, not -2.

  • Overlooking fixed-width overflow: In a 32-bit environment, shifting a sufficiently large value left can overflow. Masking with & 0xFFFFFFFF retains the unsigned 32-bit bit pattern; interpreting that mask as a signed value requires two’s-complement conversion.

  • Using multiplication instead of a shift: Although x * 2 works, x << 1 communicates the intended bit-level operation directly.

24

How do you compute the integer base-2 logarithm with bitwise operations?

The integer base-2 logarithm is the exponent of the highest set bit, or equivalently (lfloor log_2 n rfloor). Repeatedly shifting the positive integer right until it becomes 1 determines this exponent without floating-point operations.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For a positive integer (n), its binary representation contains (lfloor log_2 n rfloor + 1) bits. Each right shift by one position, n >> 1, discards the least significant bit and reduces the bit length by one.

  • Start with an exponent of 0.

  • Shift the number right while it is greater than 1.

  • Return the number of shifts.

The result is the floor of the logarithm. An exact integer logarithm exists only when (n) is a power of two.

Bitwise Operators

Operator Purpose Example
& Bitwise AND; keeps bits set in both operands 1101 & 1010 = 1000 (13 & 10 = 8)
| Bitwise OR; sets bits present in either operand 1101 | 1010 = 1111 (13 | 10 = 15)
^ Bitwise XOR; sets bits that differ 1101 ^ 1010 = 0111 (13 ^ 10 = 7)
~ Bitwise NOT; in Python, ~x == -x - 1 ~13 == -14
<< Shifts bits left, multiplying by two per position 1101 << 1 = 11010 (26)
>> Shifts bits right, dividing by two per position 1101 >> 1 = 0110 (6)

Python integers are arbitrary precision, so ~ produces a negative value rather than restricting the result to a fixed number of bits.

Step-by-Step Example

For n = 13, the target is (lfloor log_2 13 rfloor = 3):

Step Current binary value Right-shifted value Exponent
Initial 1101 — 0
1 1101 0110 1
2 0110 0011 2
3 0011 0001 3

The value has become 1, so the highest set bit was at position 3.

Code Example

def integer_log2(value: int) -> int:
    """Return floor(log2(value)) for a positive integer."""
    if value <= 0:
        raise ValueError("value must be a positive integer")

    exponent = 0
    while value > 1:
        value >>= 1
        exponent += 1

    return exponent


print(integer_log2(13))  # 3

The function handles 1 by returning 0. It rejects 0, whose logarithm is undefined, and negative integers, for which a real base-2 logarithm does not exist.

Complexity

  • Best, average, and worst time: O(log n), because the loop performs one right shift for each bit below the highest set bit. For n = 1, it completes in O(1).

  • Auxiliary space: O(1) in the usual fixed-width integer model, excluding the input and with no recursion stack.

  • Python representation: Because Python integers are arbitrary precision, the stored integer occupies O(log n) bits. If input representation and the transient shifted integer are counted, total storage is O(log n) bits; a conservative bit-level time bound is O((log n)^2) because Python may copy successively shorter integers.

Common Pitfalls

  • Floor versus exact logarithm: integer_log2(13) returns 3, although the mathematical value (log_2 13) is approximately 3.700.

  • Exact powers of two: For positive x, x & (x - 1) == 0 detects a power of two because it clears the lowest set bit.

  • Zero and negatives: Reject them explicitly rather than letting right shifts produce an incorrect result.

  • Exponentiation operator: ^ is XOR in Python, not exponentiation.

  • Built-in alternative: In ordinary Python code, value.bit_length() - 1 directly returns the same result. An interviewer asking for an implementation may expect the manual shifting algorithm.

  • Overflow: Python 3.12 does not overflow, but fixed-width languages require validation before shifting. Also remember that x & -x isolates the lowest set bit, while x ^ x always equals 0.

25

How do you detect and handle bitwise arithmetic overflow and underflow?

Integer overflow occurs when an arithmetic result falls outside the range representable by the selected bit width; underflow usually means an unsigned subtraction produces a negative result. Detect it explicitly—by checking an exact result against bounds or by using sign/carry rules—then choose to raise an error, wrap, saturate, or widen the value.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Ideas

For an unsigned width of w bits:

  • Valid range: 0 through 2^w - 1

  • Mask: (1 << w) - 1

  • Wrapped result: value & mask

For signed two’s complement with width w:

  • Valid range: -2^(w-1) through 2^(w-1) - 1

  • The highest bit is the sign bit

  • Masking produces the raw bits; subtract 2^w when the sign bit is set to decode a negative value

Python integers have arbitrary precision, so ordinary Python arithmetic does not overflow. Fixed-width checks are still needed when emulating network protocols, files, hardware registers, or other bounded formats.

Bitwise Operators

Operator Operation Important behavior
x & y Bitwise AND Selects bits set in both operands
x | y Bitwise OR Sets bits set in either operand
x ^ y Bitwise XOR Sets bits that differ; x ^ x == 0
~x Bitwise NOT In Python, ~x == -x - 1
x << n Left shift Multiplies by 2^n; does not enforce a fixed width
x >> n Right shift For n >= 0, equals floor division by 2^n; negative values retain their sign

For a bounded unsigned value, use:

wrapped = (value << shift) & 0xFFFFFFFF

Use format(0xFFFFFFFF, "08b") to display 32 binary bits; it produces 11111111111111111111111111111111.

Overflow Detection

Common detection methods are:

  • Signed addition: Inputs have the same sign, but the result has a different sign.

  • Signed subtraction: Inputs have different signs, and the result’s sign differs from the left operand, the minuend.

  • Unsigned addition: The exact sum exceeds 2^w - 1.

  • Unsigned subtraction: The right operand exceeds the left operand.

  • Range checking: Compare the exact result with the signed or unsigned limits before treating a masked value as the mathematical result.

For example, signed 32-bit addition of 0x7FFFFFFF and 1 produces the raw bits 0x80000000. The inputs are positive, but the result has its sign bit set, indicating signed overflow.

An unsigned 4-bit example illustrates the carry:

Bit Calculation Result bit Carry out
0 1 + 1 0 1
1 1 + 0 + 1 0 1
2 1 + 0 + 1 0 1
3 1 + 0 + 1 0 1

The final carry is discarded by 4-bit unsigned arithmetic, so the result overflows.

Code Example

from typing import Literal

BITS = 32
MASK = (1 << BITS) - 1
SIGN_BIT = 1 << (BITS - 1)
INT32_MIN = -(1 << (BITS - 1))
INT32_MAX = (1 << (BITS - 1)) - 1

Policy = Literal["raise", "wrap", "saturate"]


def add_i32(left: int, right: int, *, policy: Policy = "raise") -> tuple[int, bool]:
    """Add two signed 32-bit integers using two's-complement bit operations."""
    if policy not in ("raise", "wrap", "saturate"):
        raise ValueError(f"Unsupported overflow policy: {policy}")
    if not INT32_MIN <= left <= INT32_MAX:
        raise ValueError("left is outside the signed 32-bit range")
    if not INT32_MIN <= right <= INT32_MAX:
        raise ValueError("right is outside the signed 32-bit range")

    left_bits = left & MASK
    right_bits = right & MASK
    result_bits = (left_bits + right_bits) & MASK

    # Detect signed overflow from the input and result sign bits.
    overflowed = bool(
        (~(left_bits ^ right_bits) & (left_bits ^ result_bits) & SIGN_BIT)
    )

    result = result_bits - (1 << BITS) if result_bits & SIGN_BIT else result_bits

    if overflowed:
        if policy == "raise":
            raise OverflowError("signed 32-bit overflow")
        if policy == "saturate":
            result = INT32_MAX if left > 0 else INT32_MIN

    return result, overflowed


def subtract_u32(
    left: int, right: int, *, policy: Policy = "raise"
) -> tuple[int, bool]:
    """Subtract unsigned 32-bit integers, detecting an underflow."""
    if policy not in ("raise", "wrap", "saturate"):
        raise ValueError(f"Unsupported underflow policy: {policy}")
    if not 0 <= left <= MASK or not 0 <= right <= MASK:
        raise ValueError("operands must be within the unsigned 32-bit range")

    underflowed = left < right
    result = (left - right) & MASK

    if underflowed:
        if policy == "raise":
            raise ArithmeticError("unsigned 32-bit underflow")
        if policy == "saturate":
            result = 0

    return result, underflowed


print(add_i32(2147483647, 1, policy="wrap"))
# (-2147483648, True)

print(subtract_u32(1, 2, policy="wrap"))
# (4294967295, True)

Relevant edge cases include zero, exact range boundaries, positive and negative signed overflow, and unsigned underflow. Operands outside the declared range or an unsupported policy raise ValueError; raise, wrap, and saturate provide the required handling behavior.

Complexity

For fixed-width 32-bit operations:

  • Best, average and worst-case time: O(1) because a constant number of machine-sized operations are performed.

  • Auxiliary space: O(1), excluding the inputs; no recursion stack is used.

For arbitrary-precision Python integers containing B bits, additions, bitwise operations and shifts take O(B) time in the best, average and worst cases. Auxiliary space is O(B) for intermediate integer objects, excluding the input integers; there is no recursion stack. Python does not silently truncate those results.

Common Pitfalls

  • Do not mask an exact sum and then mistake the truncated value for the mathematical result. Use an exact range check or deliberately apply a sign-bit or carry formula to the truncated result.

  • ~x is not a bounded-width complement in Python. Use (~x) & MASK when working with unsigned bits.

  • | and ^ do not perform addition or carry propagation; they only combine independent bits.

  • A left shift can exceed the intended width or consume excessive memory. Validate the shift count and mask only when fixed-width wrapping is intended.

  • Distinguish signed overflow from unsigned underflow. For signed subtraction, a result below the signed minimum is normally called signed overflow.

  • Python’s arbitrary-precision integers prevent native overflow, but explicit bounds are still required for protocol-level fixed-width semantics.

26

What is the role of flags and bit checks in bitmaps?

Flags are individual bits used as compact Boolean states in a bitmap or bitset. Setting a flag preserves the other bits while turning one target bit on, while checking a bit determines whether that flag is enabled.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why Flags Matter

A bitmap stores many Boolean values more compactly than a collection of individual bytes or objects.

  • Each bit position represents one flag, feature, or membership state.

  • Setting a flag changes one state without affecting neighboring flags.

  • Checking a flag tests one state with a constant-time operation in a packed implementation.

  • Common uses include tracking visited nodes, enabled features, available items, or selected options.

For a byte-backed bitmap, bit index is stored in byte index // 8 at offset index % 8 within that byte.

Core Bit Operations

For a stored value flags and a mask 1 << offset:

  • Set: flags |= mask turns the target bit on while preserving all others.

  • Check: bool(flags & mask) reports whether the target bit is set.

  • Clear: flags &= ~mask turns the target bit off.

  • Toggle: flags ^= mask reverses the target bit.

Operator Purpose Example behavior
& Bitwise AND Keeps bits present in both operands
| Bitwise OR Sets a bit when either operand has it
^ Bitwise XOR Sets a bit when the operands differ
~ Bitwise complement In Python, ~x == -x - 1
<< Shift left For nonnegative x, x << k == x * 2**k
>> Shift right For nonnegative x, x >> k == x // 2**k

Useful related tricks include:

  • x & (x - 1) clears the lowest set bit.

  • x & -x isolates the lowest set bit.

  • x ^ x == 0 clears a flag using XOR.

  • x > 0 and x & (x - 1) == 0 tests whether x is a power of two.

  • (left ^ right).bit_count() gives the Hamming distance between two bitmasks.

  • int.bit_count() counts set bits in Python 3.10 and later.

Bit-by-Bit Example

Suppose one byte initially contains 00001010, and flag 2 must be set.

format(0b00001010, "08b") produces 00001010. The mask for bit 2 is 00000100.

Bit position Old bit Mask bit New bit
7 0 0 0
6 0 0 0
5 0 0 0
4 0 0 0
3 1 0 1
2 0 1 1
1 1 0 1
0 0 0 0

The OR result is 00001110: only the requested flag changed.

Complexity

For a fixed-size bitmap containing n flags and backed by bytearray:

  • Set, clear, toggle, and check: best, average, and worst case are all O(1) because byte indexing and bitwise updates access a fixed number of bytes.

  • Auxiliary space: O(1), excluding the bitmap itself.

  • Bitmap storage: O(n / 8) bytes, equivalent to O(n) bits.

  • Initialization: O(n / 8) time and bytes for n > 0.

Python integers are arbitrary precision and immutable. Consequently, operations on an integer bitset may take O(k) time and temporary space, where k is the number of internal machine words needed for the resulting bit length. Packed bytearray storage avoids that copying cost.

Code Example

class Bitmap:
    """Fixed-size bitmap backed by packed bytes."""

    def __init__(self, bit_count: int) -> None:
        if not isinstance(bit_count, int):
            raise TypeError("bit_count must be an integer")
        if bit_count < 0:
            raise ValueError("bit_count cannot be negative")

        self._bit_count = bit_count
        self._data = bytearray((bit_count + 7) // 8)

    def set(self, index: int) -> None:
        """Set the flag at index to 1."""
        if not 0 <= index < self._bit_count:
            raise IndexError("bit index out of range")

        byte_index = index // 8
        bit_offset = index % 8
        self._data[byte_index] |= 1 << bit_offset

    def clear(self, index: int) -> None:
        """Set the flag at index to 0."""
        if not 0 <= index < self._bit_count:
            raise IndexError("bit index out of range")

        byte_index = index // 8
        bit_offset = index % 8
        self._data[byte_index] &= ~(1 << bit_offset)

    def is_set(self, index: int) -> bool:
        """Return whether the flag at index is set."""
        if not 0 <= index < self._bit_count:
            raise IndexError("bit index out of range")

        byte_index = index // 8
        bit_offset = index % 8
        return bool(self._data[byte_index] & (1 << bit_offset))


bitmap = Bitmap(16)
bitmap.set(2)
bitmap.set(10)
bitmap.set(10)  # Setting an existing flag is idempotent.

print(bitmap.is_set(2), bitmap.is_set(4), bitmap.is_set(10))
# True False True

Common Pitfalls

  • Incorrect mask offsets: The mask is 1 << (index % 8), not 1 << index inside a byte.

  • Unsigned assumptions: Python integers are signed and arbitrary precision, so ~x is -x - 1 rather than a fixed-width complement.

  • Out-of-range indexes: Negative indexes should be rejected rather than accidentally using Python-style negative indexing.

  • Empty bitmaps: A zero-capacity bitmap has no valid flag positions.

  • Overwriting neighboring flags: Use |= rather than assigning the byte directly.

  • Common follow-up questions: Interviewers may ask how to enumerate set bits, count them, resize a bitmap, serialize it, or compare a packed bytearray implementation with a Python integer bitset.

27

How does bit manipulation speed up binary matrix multiplication?

Bit-packed matrix multiplication represents rows of one matrix and columns of the other as integer masks. A bitwise AND then identifies all positions where both operands contain 1, replacing many scalar operations with operations on machine-sized chunks of bits.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For matrices (A{m times k}) and (B{k times n}):

  1. Store row i of A as an integer mask, with bit k representing A[i][k].

  2. Store column j of B as an integer mask, with bit k representing B[k][j].

  3. Compute left_mask & right_mask. Every set bit indicates a position where A[i][k] and B[k][j] are both 1.

The final value depends on the multiplication semantics:

Semantics Result for one cell Use case
Boolean 1 if the intersection is nonzero Reachability and adjacency matrices
GF(2) Parity of the intersection XOR-based matrix multiplication
Ordinary arithmetic Number of set bits in the intersection Standard matrix multiplication

For ordinary matrix multiplication, common.bit_count() gives the required sum, although the result may exceed 1.

Bitwise Operator Toolkit

Operator Purpose Binary example
& Bitwise AND; finds positions set in both masks 1100 & 1010 = 1000
| Bitwise OR; combines set positions 1100 | 0010 = 1110
^ Bitwise XOR; computes parity 1100 ^ 1010 = 0110
~ Bitwise NOT ~0b1010 & 0xF = 0b0101
<< Shifts bits toward more significant positions 0011 << 2 = 1100
>> Shifts bits toward less significant positions 1100 >> 2 = 0011

Python integers have arbitrary precision and do not overflow. In Python, ~x equals -x - 1; mask it when working in a fixed-width two’s-complement representation, such as 32 bits with x & 0xFFFFFFFF.

Code Example

from typing import Literal


def multiply_binary_matrices(
    left: list[list[int]],
    right: list[list[int]],
    mode: Literal["boolean", "gf2"] = "boolean",
) -> list[list[int]]:
    """Multiply binary matrices using Boolean or GF(2) semantics."""
    if mode not in ("boolean", "gf2"):
        raise ValueError("mode must be 'boolean' or 'gf2'")

    if any(value not in (0, 1) for row in left for value in row):
        raise ValueError("left must contain only 0 and 1")
    if any(value not in (0, 1) for row in right for value in row):
        raise ValueError("right must contain only 0 and 1")

    if not left:
        return []

    inner_count = len(left[0])
    if any(len(row) != inner_count for row in left):
        raise ValueError("left rows must have equal lengths")
    if len(right) != inner_count:
        raise ValueError("left columns must equal right rows")

    column_count = len(right[0]) if right else 0
    if any(len(row) != column_count for row in right):
        raise ValueError("right rows must have equal lengths")

    def encode(values: list[int]) -> int:
        packed = bytearray((len(values) + 7) // 8)
        for index, value in enumerate(values):
            if value:
                packed[index // 8] |= 1 << (index % 8)
        return int.from_bytes(packed, "little")

    left_masks = [encode(row) for row in left]
    right_column_masks = [
        encode([right[row][column] for row in range(inner_count)])
        for column in range(column_count)
    ]

    result: list[list[int]] = []
    for left_mask in left_masks:
        result_row: list[int] = []
        for column_mask in right_column_masks:
            common = left_mask & column_mask
            if mode == "boolean":
                result_row.append(1 if common else 0)
            else:
                result_row.append(common.bit_count() & 1)
        result.append(result_row)

    return result


left = [[1, 1, 0], [0, 1, 1]]
right = [[1, 0, 1], [1, 1, 0], [0, 1, 1]]

print(multiply_binary_matrices(left, right))
# [[1, 1, 1], [1, 1, 1]]

print(multiply_binary_matrices(left, right, mode="gf2"))
# [[0, 1, 1], [1, 0, 1]]

print(format(0b1100 & 0b1010, "08b"))
# 00001000

Complexity

Let w be the number of bits processed in one internal integer word or limb.

  • Best, average, and worst multiplication time: (O(mnlceil k/wrceil)), because each cell performs an AND over at most (k) bits; GF(2) additionally counts the set bits.

  • Mask construction: (O(mk + kn)).

  • Total time for square matrices: (O(n^2 + n^3/w)), conventionally written as (O(n^3/w)) for the multiplication phase.

  • Auxiliary space: (O((m+n)lceil k/wrceil)) for masks.

  • Output space: (O(mn)), with the returned matrix included.

  • Recursion stack: (O(1)).

These bounds exclude the input matrices. With fixed-size machine words, the asymptotic worst case remains cubic, but bit packing reduces the constant factor substantially.

Example Walkthrough

Using the first row of left:

Right column Left mask Column mask AND Set bits Boolean GF(2)
0 011 011 011 2 1 0
1 011 110 010 1 1 1
2 011 101 001 1 1 1

Thus, the first output row is [1, 1, 1] under Boolean semantics and [0, 1, 1] under GF(2).

Common Pitfalls

  • Choose the correct semantics: Boolean multiplication uses existence, GF(2) uses parity, and arithmetic multiplication uses the count.

  • Keep bit positions aligned: Row masks and column masks must use the same inner index as their bit position.

  • Avoid negative shifts: In Python, shifting by a negative amount raises ValueError.

  • Remember Python’s NOT behavior: ~x is -x - 1, not merely the bit pattern of x within its current width.

  • Validate inputs: Negative or non-binary values are rejected; duplicate matrix positions remain distinct and contribute separately.

  • Edge cases: Empty matrices produce correctly shaped empty results, zero-column matrices produce empty rows, and a 1 × 1 matrix follows the same mask logic. Sorting, disconnected graphs, and cycles are not applicable to matrix multiplication.

  • A common interview follow-up asks how to transpose or encode matrices as masks efficiently using blocks of w bits.

28

How can bit manipulation convert between big- and little-endian byte order?

Endian conversion can be implemented as a byte swap: each byte’s internal bits remain unchanged, but the order of the bytes is reversed. The operation is its own inverse, so the same algorithm performs both big-to-little and little-to-big conversion for a fixed-width integer.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Key Idea

Treat the integer as a sequence of width_bytes bytes. Repeatedly:

  1. Extract the least-significant byte with value & 0xFF.

  2. Append it to the result using result = (result << 8) | byte.

  3. Remove the extracted byte with value >>= 8.

For a 32-bit value, this is equivalent to:

((x & 0x000000FF) << 24) |
((x & 0x0000FF00) << 8)  |
((x & 0x00FF0000) >> 8)  |
((x & 0xFF000000) >> 24)

Endianness changes byte order, not the bit order within each byte.

Bit-Manipulation Operators

Operator Purpose Example or rule
& Bitwise AND x & 0xFF extracts the lowest byte.
| Bitwise OR Combines non-overlapping byte fields.
^ Bitwise XOR x ^ x == 0; useful for clearing equal bits.
~ Bitwise inversion In Python, ~x == -x - 1.
<< Left shift result << 8 appends eight zero bits.
>> Right shift value >> 8 removes the lowest byte.

Python integers have arbitrary precision and do not overflow. For explicit 32-bit two’s-complement handling, convert the raw representation with x & 0xFFFFFFFF and then interpret the highest bit when a signed result is required.

Algorithm Walkthrough

For 0x12345678, the algorithm extracts bytes from least significant to most significant:

Step Extracted byte Remaining value Accumulated result
1 0x78 0x123456 0x78
2 0x56 0x1234 0x7856
3 0x34 0x0012 0x785634
4 0x12 0x0000 0x78563412

The lowest-byte extraction can be inspected bit by bit:

Bit 7 6 5 4 3 2 1 0
0x78 0 1 1 1 1 0 0 0
0xFF 1 1 1 1 1 1 1 1
0x78 & 0xFF 0 1 1 1 1 0 0 0

Complexity

For a width of w bytes:

  • Best, average and worst time: O(w), because each byte is extracted once.

  • Auxiliary space: O(1) fixed-width words for a machine-word-sized value; the input is not counted, and there is no recursion stack.

  • Under Python’s arbitrary-precision bit-cost model, very large widths take up to O(w²) bit operations and O(w) bits of auxiliary storage.

Code Example

def swap_byte_order(
    value: int,
    width_bytes: int = 4,
    *,
    signed: bool = False,
) -> int:
    """Swap bytes in a fixed-width unsigned or two's-complement integer."""
    if width_bytes <= 0:
        raise ValueError("width_bytes must be positive")

    bit_count = width_bytes * 8
    modulus = 1 << bit_count

    if signed:
        minimum = -(1 << (bit_count - 1))
        maximum = (1 << (bit_count - 1)) - 1
    else:
        minimum = 0
        maximum = modulus - 1

    if not minimum <= value <= maximum:
        raise ValueError(f"value must be between {minimum} and {maximum}")

    # Obtain the raw fixed-width two's-complement representation.
    raw_value = value & (modulus - 1)
    result = 0

    for _ in range(width_bytes):
        result = (result << 8) | (raw_value & 0xFF)
        raw_value >>= 8

    # Interpret the swapped representation as signed when requested.
    if signed and result & (1 << (bit_count - 1)):
        result -= modulus

    return result


print(f"0x{swap_byte_order(0x12345678, 4):08X}")  # 0x78563412
print(f"0x{swap_byte_order(0x78563412, 4):08X}")  # 0x12345678
print(swap_byte_order(-1, 4, signed=True))        # -1
print(format(0x78, "08b"))                       # 01111000

Common Pitfalls

  • Wrong width: The byte width must be fixed. Swapping 4 bytes is not equivalent to swapping 8 bytes.

  • Signed values: Unsigned mode rejects negative inputs; signed mode interprets the highest bit as two’s-complement sign.

  • Edge cases: Zero is unchanged, a one-byte value is unchanged, and identical bytes remain identical after swapping. An empty input is not applicable to a scalar integer.

  • Direction confusion: Applying the swap twice restores the original value.

  • Related interview tricks: x & (x - 1) clears the lowest set bit, x & -x isolates it, and x > 0 and x & (x - 1) == 0 tests whether x is a power of two. Python 3.12 also provides int.bit_count() for counting set bits.

29

What is a simple bitwise compression algorithm, with an example?

A simple example is bit packing, which stores an ordered collection of Boolean flags using one bit per flag instead of one byte per flag. It uses shifts and masks to place each flag at the correct position within a bytes object.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For flag index i:

  • i // 8 identifies the output byte containing the flag.

  • i % 8 identifies the flag’s position within that byte.

  • 1 << (i % 8) creates a mask containing only that bit.

  • | sets the bit when the flag is True.

  • & reads the bit during decompression.

For example, eight Boolean flags occupy one byte, giving an eightfold reduction compared with a byte-per-flag representation. This is useful for compactly storing feature flags, sensor states, permission indicators, or protocol headers.

Bitwise Operators and Common Tricks

Using x = 0b00000011 and y = 0b00000101:

Operator Operation Example result
& Bitwise AND x & y → 0b00000001
| Bitwise OR x | y → 0b00000111
^ Bitwise XOR x ^ y → 0b00000110
~ Bitwise NOT ~x → -4, or -0b100
<< Shift bits left x << 1 → 0b00000110
>> Shift bits right x >> 1 → 0b00000001

Python integers have arbitrary precision, so they do not overflow. Consequently, ~x == -x - 1; to view the result as an eight-bit value, use (~x) & 0xFF.

Related interview tricks include:

  • x & (x - 1) clears the lowest set bit.

  • x & -x isolates the lowest set bit.

  • x ^ x is always 0.

  • x > 0 and x & (x - 1) == 0 checks whether x is a power of two.

  • x.bit_count() counts set bits in Python 3.10 and later.

Example Walkthrough

This table shows how eight flags are packed into one byte:

Index Flag Bit mask Byte after update
0 True 00000001 00000001
1 False 00000010 00000001
2 True 00000100 00000101
3 True 00001000 00001101
4 False 00010000 00001101
5 False 00100000 00001101
6 False 01000000 00001101
7 True 10000000 10001101

The resulting byte is 0b10001101, or hexadecimal 0x8D.

Complexity and Edge Cases

For n flags:

Operation Best time Average time Worst time Space
Pack O(n) O(n) O(n) O(n) for the output; O(1) auxiliary space
Unpack O(n) O(n) O(n) O(n) for the returned list; O(1) auxiliary space

Every flag is inspected, so all three time bounds are the same. There is no recursion stack. The input is not counted in the auxiliary-space figures; including the input and output still gives O(n) total storage.

  • Empty input: Packing returns b""; unpacking zero flags returns [].

  • One element: It occupies the least significant bit of the first byte.

  • Duplicates and order: Repeated flags are preserved in their original positions.

  • Negative numbers: They are rejected because the algorithm accepts Boolean values only.

  • Sorting, disconnected graphs, and cycles: These concepts do not apply to this operation.

  • The input list is not mutated.

Common Pitfalls

  • Losing the element count: This compact format does not store count; a real file format should include it in a header.

  • Incorrect bit order: The lowest bit represents index 0. Changing the convention requires changing both packing and unpacking.

  • Unmasked ~: Python’s ~ produces an infinite signed result, not a fixed-width byte.

  • Assuming general-purpose compression: Bit packing helps when data has many one-bit values. It provides little benefit for arbitrary bytes and no compression for already-dense data.

  • Interview follow-ups: Expect questions about variable-width packing, endianness, signed values, malformed input, and why run-length encoding or entropy coding may be more appropriate for repeated or skewed data.

30

How do bitwise operations encode and decode packed data?

Yes. Bit packing stores multiple fixed-width values in a single byte or integer by shifting each value into its assigned bit range and using masks to extract it later. This can reduce storage and make field access efficient, although it does not automatically compress arbitrary data or provide encryption.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Bit Packing Works

Each field receives a fixed number of bits. For example, two values between 0 and 15 can occupy separate 4-bit fields in one byte:

  • The low four bits store the first value.

  • The high four bits store the second value.

  • Encoding uses << to position a value and | to insert it.

  • Decoding uses >> to select the field and & 0x0F to remove unrelated bits.

The decoder must know the expected number of fields because an unused high nibble cannot reveal whether the original data contained an odd or even number of values.

Bitwise Operators

  • & — AND: Keeps only bits enabled in both operands. It implements masking.

  • | — OR: Combines fields by setting their bits independently.

  • ^ — XOR: Toggles differing bits and cancels matching bits. x ^ x is 0.

  • ~ — NOT: Inverts bits. In Python, ~x == -x - 1; for an 8-bit result, use (~x) & 0xFF.

  • << — Left shift: Multiplies an unsigned value by a power of two.

  • >> — Right shift: Divides an unsigned value by a power of two, discarding remainder bits.

Python integers have arbitrary precision and do not overflow. To retain only a 32-bit value, use x & 0xFFFFFFFF. If interpreted as signed two’s complement, subtract 2**32 when the result is at least 2**31.

Bit-by-Bit Example

format(0x53, "08b") produces 01010011. Extracting the low nibble gives 3:

Bit 7 6 5 4 3 2 1 0
0x53 0 1 0 1 0 0 1 1
0x0F 0 0 0 0 1 1 1 1
0x53 & 0x0F 0 0 0 0 0 0 1 1

The result is 0x03. Shifting right by four bits similarly extracts 0x05 from the high nibble.

Code Example

from collections.abc import Sequence


def encode_nibbles(values: Sequence[int]) -> bytes:
    """Pack values from 0 through 15 into consecutive 4-bit fields."""
    if any(value < 0 or value > 15 for value in values):
        raise ValueError("Each value must be between 0 and 15")

    packed = bytearray((len(values) + 1) // 2)

    for index, value in enumerate(values):
        byte_index = index // 2
        shift = 4 * (index % 2)
        packed[byte_index] |= value << shift

    return bytes(packed)


def decode_nibbles(packed: bytes, count: int) -> tuple[int, ...]:
    """Decode count values from consecutive 4-bit fields."""
    if count < 0 or count > len(packed) * 2:
        raise ValueError("Invalid field count")

    values = []
    for index in range(count):
        byte = packed[index // 2]
        shift = 4 * (index % 2)
        values.append((byte >> shift) & 0x0F)

    return tuple(values)


values = (3, 5, 10, 15)
packed = encode_nibbles(values)
decoded = decode_nibbles(packed, len(values))
print(f"{packed.hex()} {decoded}")
# 53fa (3, 5, 10, 15)

Complexity and Edge Cases

Approach Best, Average, Worst Time Space When to Use
One byte per value O(n) n bytes Values require all 8 bits
Two 4-bit fields per byte O(n) ⌈n/2⌉ bytes Values are between 0 and 15

Each loop iteration performs constant-width byte operations, so encoding and decoding both take O(n) time in the best, average, and worst cases. Storage is O(n) bytes, including the output; additional working space is O(1). The input is excluded from auxiliary-space measurements, and there is no recursion stack.

Empty input is supported, one-element values work, duplicates are preserved, and negative or oversized values are rejected. The odd-field case leaves the unused high nibble zero. Accumulating all fields in one growing Python integer would instead cause O(n²) worst-case bit work because Python integers are arbitrary precision.

Common Pitfalls

  • Always mask decoded fields; otherwise neighboring bits can contaminate the result.

  • Store the field count separately when the final field may be zero or unused.

  • XOR is useful for toggling and checksums, but it is not secure encryption.

  • x & (x - 1) clears the lowest set bit.

  • x & -x isolates the lowest set bit.

  • x > 0 and (x & (x - 1)) == 0 tests whether x is a power of two.

  • Use int.bit_count() in Python 3.10+ to count set bits efficiently.

31

How do bitwise operations support Huffman coding and compression?

Bitwise operations let compression algorithms construct, pack, inspect, and manipulate individual bits efficiently. In Huffman coding, the entropy model determines variable-length codes, while bitwise operations handle their compact binary representation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Bitwise Operations Support Huffman Coding

Huffman coding assigns a prefix-free code to each symbol based on its frequency:

  • Frequent symbols receive short codes.

  • Rare symbols receive long codes.

  • The code tree represents each symbol as a path of 0 and 1 edges.

Tree construction does not inherently require bitwise operators; codes could be stored as strings. Bitwise operations become useful when codes are packed into bytes or processed as bit streams.

The main operators are:

  • Shift left, <<: Appends a bit or multiplies an integer by a power of two.

  • Bitwise OR, |: Merges values or sets selected bits.

  • Bitwise AND, &: Extracts selected bits using a mask.

  • Bitwise XOR, ^: Toggles differing bits without carries.

  • Right shift, >>: Discards low-order bits or extracts higher-order fields.

  • Bitwise NOT, ~: Inverts bits.

Bitwise Operator Toolkit

Operator Meaning Compression use
x & mask Keeps only masked bits Extract flags or byte fields
x | value Sets selected bits Append bits or merge fields
x ^ y Toggles differing bits XOR-delta encoding and checksums
~x Inverts bits Inverting a mask
x << n Moves bits left Packing integers and bytes
x >> n Moves bits right Reading fields and decoding streams

For example, format(5, '04b') is 0101, while format(3, '04b') is 0011:

Bit position 5 3 5 & 3
3 0 0 0
2 1 0 0
1 0 1 0
0 1 1 1

Therefore, 5 & 3 == 1.

Useful bit tricks include:

  • x & (x - 1) clears the lowest set bit.

  • x & -x isolates the lowest set bit.

  • x ^ x == 0 because identical bits cancel.

  • x > 0 and x & (x - 1) == 0 tests whether x is a power of two.

  • int.bit_count() counts set bits in Python 3.10 and later.

Python integers have arbitrary precision, so overflow does not occur. Also, ~x == -x - 1; to obtain an unsigned 32-bit value, use x & 0xFFFFFFFF.

Worked Example

For b"banana", the frequencies are b: 1, a: 3, and n: 2. One valid Huffman tree produces:

Symbol Frequency Code
a 3 0
b 1 10
n 2 11

Encoding banana concatenates 10, 0, 11, 0, 11, and 0, producing 100110110. Those 9 bits fill one byte (10011011 = 0x9b) plus one bit; padding the second byte with seven zero bits gives 00000000, so the packed bytes are 9b00.

Code Example

from collections import Counter
from dataclasses import dataclass, field
from heapq import heappop, heappush


@dataclass(order=True)
class Node:
    frequency: int
    tie_breaker: int = field(compare=False)
    value: int | None = field(default=None, compare=False)
    left: "Node | None" = field(default=None, compare=False)
    right: "Node | None" = field(default=None, compare=False)


def huffman_encode(data: bytes) -> tuple[bytes, dict[int, str]]:
    """Return Huffman-packed bytes and the code assigned to each byte value."""
    if not data:
        raise ValueError("data must not be empty")

    frequencies = Counter(data)

    if len(frequencies) == 1:
        codes = {next(iter(frequencies)): "0"}
    else:
        heap: list[Node] = []
        tie_breaker = 0

        for value, frequency in frequencies.items():
            heappush(heap, Node(frequency, tie_breaker, value=value))
            tie_breaker += 1

        while len(heap) > 1:
            left = heappop(heap)
            right = heappop(heap)
            heappush(
                heap,
                Node(
                    left.frequency + right.frequency,
                    tie_breaker,
                    left=left,
                    right=right,
                ),
            )
            tie_breaker += 1

        root = heap[0]
        codes: dict[int, str] = {}
        stack: list[tuple[Node, str]] = [(root, "")]

        while stack:
            node, prefix = stack.pop()

            if node.value is not None:
                codes[node.value] = prefix
            else:
                assert node.left is not None and node.right is not None
                stack.append((node.right, prefix + "1"))
                stack.append((node.left, prefix + "0"))

    packed = bytearray()
    buffer = 0
    buffered_bits = 0

    for value in data:
        for bit in codes[value]:
            # Append one bit at the right side of the byte.
            buffer = (buffer << 1) | int(bit)
            buffered_bits += 1

            if buffered_bits == 8:
                packed.append(buffer)
                buffer = 0
                buffered_bits = 0

    if buffered_bits:
        # Pad the final byte with zero bits.
        packed.append(buffer << (8 - buffered_bits))

    return bytes(packed), codes


encoded, codes = huffman_encode(b"banana")
print(encoded.hex())  # Expected: 9b00

Complexity

Let m be the input length, u the number of distinct symbols, B the emitted data bits, and S the sum of all generated code lengths.

  • Frequency counting takes O(m) time because each byte is counted once.

  • Tree construction takes O(u log u) time because the heap performs u - 1 merges.

  • Code generation takes O(S) time and retains O(S) space.

  • Encoding takes O(m + B) time because every emitted bit is processed.

Overall time is O(m + u log u + S + B). It is O(m + u log u) in the best case, O(m log u) for approximately uniform symbols on average, and O(mu) in the worst case. Total space is O(S + u + B), excluding the input: O(u log u + B) in the best and uniform-average cases and O(u² + B) in the worst case. The iterative traversal avoids Python’s recursion-depth limit.

Common Pitfalls and Interview Tips

  • Padding ambiguity: Store the original length or use an end marker so the decoder can distinguish padding from data.

  • Wrong bit order: Specify whether bits are packed most-significant-bit first.

  • Applicable edge cases: Empty data raises ValueError; one distinct byte uses a one-bit code; duplicate bytes contribute to one symbol’s frequency; sorted or unsorted input order does not affect optimality. Negative values and graph-specific disconnected or cycle cases are outside this byte-string API.

  • Python ~ behavior: Remember ~x == -x - 1, not fixed-width inversion.

  • Huffman is not encryption: It reduces average code length but provides no confidentiality.

  • Common follow-up: Interviewers may ask about canonical Huffman codes, entropy bounds, or why XOR-delta encoding works through current = previous ^ delta.

32

How does bit manipulation support Base64 encoding and decoding?

Base64 uses bit manipulation to repackage binary data into printable ASCII characters. It groups bytes into six-bit values, maps each value to an alphabet character, and reverses the process during decoding.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Base64 Uses Bits

Each non-padding Base64 character represents a 6-bit value:

  • Complete input group: 3 bytes = 24 data bits.

  • Complete output group: 4 characters = 24 data bits.

  • Alphabet: A-Z, a-z, 0-9, +, and /; URL-safe Base64 uses - and _ instead.

  • Padding: = marks missing input bytes in the final incomplete group.

For example, "Man" has these bytes and bit contributions:

Byte Binary Bits carried into groups Six-bit values Characters
M 01001101 010011; leaves 01 010011 = 19 T
a 01100001 Joins 01 with 0110; leaves 0001 010110 = 22 W
n 01101110 Joins 0001 with 01; leaves 101110 000101 = 5; 101110 = 46 Fu

Therefore, "Man" becomes TWFu. In Python, format(0x4D, "08b") displays M as '01001101'.

Relevant Bitwise Operators

Operator Meaning Use in Base64 or related work
& Bitwise AND Masks a value to the required number of bits, such as (value >> 18) & 0x3F.
| Bitwise OR Combines separately positioned bit fields into one integer.
^ Bitwise XOR Toggles differing bits; x ^ x is 0 for a single number. It is not required by Base64 itself.
~ Bitwise inversion Inverts every bit. Python uses arbitrary-precision integers, so ~x equals -x - 1; this differs from inversion within a fixed-width field.
<< Left shift Moves bits toward more significant positions.
>> Right shift Moves bits toward less significant positions so a 6-bit field can be extracted.

Other useful bit tricks include x & (x - 1), which clears the lowest set bit; x & -x, which isolates the lowest set bit; and x.bit_count(), which counts set bits.

Encoding and Decoding Steps

  1. Split the input into groups of up to three bytes.

  2. For a complete group, concatenate its 24 bits. For a final one- or two-byte group, append zero bits only until the bit count is a multiple of six.

  3. Split the bits into four 6-bit values.

  4. Map each value to its Base64 alphabet character.

  5. Add one = for each missing input byte: two for one byte and one for two bytes.

Decoding maps characters back to 6-bit values, concatenates them, splits them into bytes, and removes the bytes represented by padding.

Base64 is an encoding, not encryption or an integrity mechanism. Anyone who knows the alphabet can decode it.

Complexity and Trade-offs

Operation Best Average Worst Space
Encode O(n) O(n) O(n) O(n), including the result and intermediate character list
Decode O(n) O(n) O(n) O(n), including decoded output and intermediate values

Each input byte or Base64 character is processed a constant number of times. There is O(1) recursion stack space because the implementation is iterative. The original input is not mutated and is not counted as auxiliary space.

Base64 increases size by approximately 33% because every 3 bytes become 4 characters. It is useful for transmitting binary data through text-only channels such as JSON, email, or XML; binary-native protocols avoid this expansion.

Code Example

from typing import Final

_ALPHABET: Final = (
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    "abcdefghijklmnopqrstuvwxyz"
    "0123456789+/"
)
_ALPHABET_INDEX: Final = {
    character: index for index, character in enumerate(_ALPHABET)
}


def encode_base64(data: bytes) -> str:
    """Encode bytes as padded Base64 using six-bit groups."""
    encoded: list[str] = []

    for offset in range(0, len(data), 3):
        chunk = data[offset : offset + 3]
        padded = chunk + b"\x00" * (3 - len(chunk))
        value = int.from_bytes(padded, "big")

        characters = [
            _ALPHABET[(value >> 18) & 0x3F],
            _ALPHABET[(value >> 12) & 0x3F],
            _ALPHABET[(value >> 6) & 0x3F],
            _ALPHABET[value & 0x3F],
        ]

        if len(chunk) == 1:
            encoded.extend((characters[0], characters[1], "=", "="))
        elif len(chunk) == 2:
            encoded.extend((characters[0], characters[1], characters[2], "="))
        else:
            encoded.extend(characters)

    return "".join(encoded)


def decode_base64(text: str) -> bytes:
    """Decode padded Base64 and reject malformed or non-canonical input."""
    if len(text) % 4 != 0:
        raise ValueError("Base64 length must be a multiple of four")

    body = text
    padding = 0

    while body.endswith("="):
        body = body[:-1]
        padding += 1

    if padding > 2:
        raise ValueError("Base64 may contain at most two padding characters")

    if any(character not in _ALPHABET_INDEX for character in body):
        raise ValueError("Text contains a non-Base64 character")

    values = [_ALPHABET_INDEX[character] for character in body]

    # Reject non-zero bits that would be discarded by padding.
    if padding and values:
        unused_mask = 0b11 if padding == 1 else 0b1111
        if values[-1] & unused_mask:
            raise ValueError("Base64 contains non-zero unused bits")

    decoded = bytearray()

    for offset in range(0, len(values), 4):
        group = values[offset : offset + 4]
        group.extend([0] * (4 - len(group)))

        value = (
            (group[0] << 18)
            | (group[1] << 12)
            | (group[2] << 6)
            | group[3]
        )

        decoded.append((value >> 16) & 0xFF)
        decoded.append((value >> 8) & 0xFF)
        decoded.append(value & 0xFF)

    return bytes(decoded[: len(decoded) - padding])


print(encode_base64(b"Man"))           # TWFu
print(decode_base64("TWFu"))           # b'Man'

Common Pitfalls and Interview Tips

  • Do not treat Base64 as encryption: it provides encoding, not confidentiality.

  • Preserve bit order: Base64 processes bits from most significant to least significant.

  • Handle padding correctly: one missing byte (two bytes present) produces =; two missing bytes (one byte present) produce ==.

  • Remember arbitrary precision: Python integers do not overflow, but fixed-width languages may need masking such as value & 0xFFFFFFFF.

  • Use the standard library in production: Python’s base64.b64encode() and base64.b64decode(data, validate=True) are safer and faster than a custom implementation.

  • Common follow-up: explain why Base64 expands data by one-third, or how base64.urlsafe_b64encode() differs from standard Base64.

33

How can bitmasks store multiple boolean flags in one byte?

Bitmasking stores multiple boolean flags as individual bits in one byte: a set bit represents True, while a clear bit represents False. Bitwise operations can inspect, set, clear, or toggle selected flags without changing the others.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A byte contains eight bits, numbered from 0 at the least-significant or rightmost position to 7 at the leftmost position. Each bit can independently represent one flag.

A one-bit mask is created by shifting 1 into the required position:

  • 1 << 0 creates mask 00000001.

  • 1 << 1 creates mask 00000010.

  • 1 << 2 creates mask 00000100.

  • 1 << 7 creates mask 10000000.

The usual state operations are:

  • Check: state & mask is nonzero when the flag is enabled.

  • Set: state | mask enables the flag.

  • Clear: state & ~mask disables the flag.

  • Toggle: state ^ mask reverses the flag.

Because each operation uses a mask, flags that are not selected remain unchanged.

Bitwise Operators

Operator Operation Use with flags
& AND Tests whether selected bits are set
| OR Sets selected bits
^ XOR Toggles selected bits
~ NOT Produces the complement used when clearing bits
<< Left shift Creates a mask at a particular position
>> Right shift Moves a bit into the least-significant position for inspection

In Python, ~x equals -x - 1, and integers have arbitrary precision. To complement only the eight bits of a byte, use (~x) & 0xFF.

Useful related tricks include:

  • x & (x - 1) clears the lowest set bit.

  • For nonzero x, x & -x isolates the lowest set bit; for x == 0, it returns 0.

  • x > 0 and (x & (x - 1)) == 0 tests whether a positive integer is a power of two.

  • x ^ x equals 0; therefore, toggling the same flag twice restores it.

  • (x & 0xFF).bit_count() counts the enabled flags in a byte.

Bit-by-Bit Example

Suppose READ uses bit 0 and EXECUTE uses bit 2. The initial state is 00101000.

State Bit 7 Bit 6 Bit 5 Bit 4 Bit 3 Bit 2 Bit 1 Bit 0
Initial 0 0 1 0 1 0 0 0
Set READ 0 0 1 0 1 0 0 1
Toggle EXECUTE 0 0 1 0 1 1 0 1

The final byte is 00101101, or 0x2D in hexadecimal.

Code Example

READ = 1 << 0
WRITE = 1 << 1
EXECUTE = 1 << 2
DELETE = 1 << 3


def is_flag_set(state: int, mask: int) -> bool:
    """Return whether the single-bit mask is enabled in state."""
    if not 0 <= state <= 0xFF:
        raise ValueError("state must fit in one unsigned byte")
    if not 1 <= mask <= 0xFF or (mask & (mask - 1)) != 0:
        raise ValueError("mask must contain exactly one set bit")

    return (state & mask) != 0


def update_flags(
    state: int,
    *,
    set_mask: int = 0,
    clear_mask: int = 0,
    toggle_mask: int = 0,
) -> int:
    """Update an unsigned byte by setting, clearing, then toggling flags."""
    if not 0 <= state <= 0xFF:
        raise ValueError("state must fit in one unsigned byte")

    for mask in (set_mask, clear_mask, toggle_mask):
        if not 0 <= mask <= 0xFF:
            raise ValueError("each mask must fit in one unsigned byte")

    updated = (state | set_mask) & 0xFF
    updated = (updated & (~clear_mask)) & 0xFF
    updated = (updated ^ toggle_mask) & 0xFF
    return updated


initial = 0b00101000
updated = update_flags(
    initial,
    set_mask=READ,
    toggle_mask=EXECUTE,
)

print(format(updated, "08b"))  # Expected output: 00101101

Complexity

For a fixed one-byte state, the best, average, and worst-case time complexity are all O(1) because only a constant number of bitwise operations are performed. Auxiliary space is O(1) because the result and intermediate values use constant space; the input is not counted, and there is no recursion stack.

Common Pitfalls

  • Bit numbering: Bit 0 is the rightmost, least-significant bit in a conventional binary representation.

  • Unmasked complements: ~state includes bits above the byte in Python; combine it with 0xFF.

  • Invalid masks: 1 << 8 does not fit in one byte. Reject or mask it explicitly.

  • Overlapping masks: update_flags applies operations in set, clear, then toggle order, so an overlapping clear undoes an earlier set.

  • Repeated operations: Setting or clearing the same bit repeatedly is idempotent, but toggling it repeatedly changes the final value according to parity.

  • Edge states: 0x00 represents no enabled flags, while 0xFF represents all eight flags enabled. Negative states or masks are rejected.

34

How is bit manipulation used in network packet creation and parsing?

Bit manipulation represents compact protocol fields—such as flags, versions, lengths, and addresses—as individual bits within larger integers. This allows network software to construct headers efficiently and extract fields using masks and shifts while respecting each protocol’s byte order.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why Network Protocols Use Bits

Network headers often contain fields smaller than one byte. Packing several fields into a byte or integer:

  • Reduces packet size.

  • Defines an exact, deterministic wire format.

  • Allows fast extraction of flags and other small fields.

  • Supports fixed-width values required by protocols such as IPv4, IPv6, TCP, and UDP.

The protocol specification determines the field widths and bit positions. A programmer must not choose an arbitrary layout.

Core Bitwise Operators

For integer values x and y:

  • x & y: Keeps a bit set only when the corresponding bits are set in both operands. This is used to extract a field after shifting it into the lowest positions.

  • x | y: Sets a bit when it is set in either operand. This is commonly used to combine independent flags.

  • x ^ y: Sets a bit when the operands differ. It can toggle flags.

  • ~x: Inverts every bit. In Python, integers have arbitrary precision, so ~x == -x - 1; for example, ~5 == -6. To invert a fixed-width field, mask the result: (~flags) & 0x0F.

  • x << k: Shifts bits left by k positions, inserting zero bits on the right. This moves a field into a larger integer.

  • x >> k: Shifts bits right by k positions. Python uses arithmetic right shift for signed integers.

Example values can be displayed with format(value, "08b") or bin(value).

Bit-by-Bit Example

The following operation combines the ACK and FIN flags:

Value Binary
ACK = 0x01 00000001
FIN = 0x02 00000010
ACK | FIN 00000011

The | operation preserves both independent bits.

Packet Bit Layout

The example protocol below uses a 32-bit control word:

Bits Field Width Mask
31–24 Magic 8 0xFF000000
23–20 Version 4 0x00F00000
19–16 Flags 4 0x000F0000
15–0 Payload length 16 0x0000FFFF

struct.pack("!I", value) and struct.unpack("!I", data) handle the four-byte, big-endian network representation. The fields inside the integer are still accessed with shifts and masks.

Code Example

import struct
from typing import NamedTuple

PACKET_MAGIC = 0xB0
PACKET_VERSION = 1

FLAG_ACK = 0x01
FLAG_FIN = 0x02


class PacketHeader(NamedTuple):
    magic: int
    version: int
    flags: int
    payload_length: int


def create_packet(payload: bytes, flags: int = 0) -> bytes:
    """Create one packet frame with a four-byte control header."""
    if not 0 <= flags <= 0x0F:
        raise ValueError("flags must fit in four bits")
    if len(payload) > 0xFFFF:
        raise ValueError("payload exceeds the 16-bit length field")

    control_word = (
        (PACKET_MAGIC << 24)
        | (PACKET_VERSION << 20)
        | (flags << 16)
        | len(payload)
    )

    # "!I" encodes an unsigned 32-bit integer in network byte order.
    return struct.pack("!I", control_word) + payload


def parse_packet(packet: bytes) -> tuple[PacketHeader, bytes]:
    """Validate and decode one packet frame."""
    if len(packet) < 4:
        raise ValueError("packet is shorter than its header")

    control_word = struct.unpack("!I", packet[:4])[0]

    magic = (control_word >> 24) & 0xFF
    version = (control_word >> 20) & 0x0F
    flags = (control_word >> 16) & 0x0F
    payload_length = control_word & 0xFFFF

    if magic != PACKET_MAGIC:
        raise ValueError("invalid packet magic")
    if version != PACKET_VERSION:
        raise ValueError("unsupported packet version")
    if len(packet) != 4 + payload_length:
        raise ValueError("declared payload length does not match packet size")

    header = PacketHeader(magic, version, flags, payload_length)
    return header, packet[4:]


packet = create_packet(b"hello", flags=FLAG_ACK | FLAG_FIN)
header, payload = parse_packet(packet)

print(header)
print(payload)

# Expected output:
# PacketHeader(magic=176, version=1, flags=3, payload_length=5)
# b'hello'

Complexity

For a packet containing n payload bytes:

  • Best, average, and worst-case time: O(n) for creation and parsing because Python copies the payload into the resulting packet or payload slice. Header manipulation itself is O(1).

  • Auxiliary space: O(1) when the supplied input and returned packet are excluded. Including the input and output data, space is O(n).

  • Recursion stack: O(1) because neither function is recursive.

Common Pitfalls

  • Wrong byte order: Network protocols commonly use big-endian order. Python’s !I (equivalent to >I) selects big-endian network byte order, while <I is little-endian and @I or plain I uses the platform’s native order.

  • Incorrect field masks: Always mask after shifting so that neighboring fields do not leak into the result.

  • Unbounded complement: ~flags produces a negative Python integer. Apply & 0x0F when working with a four-bit field.

  • Trusting declared lengths: Validate the packet size before slicing or allocating based on untrusted network data.

  • Manual pointer casts: Prefer struct over reading packed binary data through raw memory layouts, which can introduce alignment and endianness errors.

  • Unsigned overflow assumptions: Python integers do not overflow, but other languages and fixed-width protocol fields can.

35

How do I implement modular exponentiation using bit manipulation?

Modular exponentiation computes (base^{exponent} bmod modulus) efficiently by processing the exponent one binary digit at a time. Repeated squaring reduces the number of multiplications from (O(exponent)) to (O(log exponent)).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm maintains the invariant:

[ result times base^{exponent} equiv originalBase^{originalExponent} pmod{modulus} ]

For each iteration:

  1. If the least significant bit of exponent is 1, multiply result by base.

  2. Reduce result modulo modulus.

  3. Square base and reduce it modulo modulus.

  4. Shift exponent right by one bit.

  5. Continue until exponent becomes zero.

This is called binary exponentiation or the square-and-multiply algorithm.

Operator Reference

With x = 0b1010 and y = 0b0101:

Operator Purpose Example
& Bitwise AND; detects the lowest set bit x & 1 == 0
| Bitwise OR; sets selected bits x | 1 == 0b1011
^ Bitwise XOR; toggles selected bits x ^ x == 0
~ Bitwise NOT ~10 == -11 in Python
<< Shift bits left; equivalent to multiplication by (2^k) x << 1 == 0b10100
>> Shift bits right; equivalent to division by (2^k) x >> 1 == 0b0101

A bit-by-bit example for x = 1010 and y = 0101:

Bit position 3 2 1 0
x 1 0 1 0
y 0 1 0 1
x & y 0 0 0 0
x | y 1 1 1 1
x ^ y 1 1 1 1

Python integers have arbitrary precision, so there is no overflow. Consequently, ~x equals -x - 1, not simply the finite-width complement. For explicit 32-bit two’s-complement handling, mask values with 0xFFFFFFFF.

Complexity

Let (e) be the exponent and (k) the bit length of the modulus.

  • Best case: (O(log e)), because the loop runs once per exponent bit.

  • Average case: (O(log e)).

  • Worst case: (O(log e)).

  • Auxiliary space: (O(1)) integer variables under the usual unit-cost model, excluding the input. With arbitrary-precision integers, the actual storage is (O(k)) bits because a constant number of (O(k))-bit values are retained.

In strict bit-complexity terms, each iteration includes a multiplication and modulo operation, so the cost also depends on the operand sizes, not only the number of iterations. An exponent of zero takes (O(1)) time.

Example Walkthrough

Compute (3^{13} bmod 5). The exponent 13 is 1101 in binary, so its bits are processed from least significant to most significant.

Exponent before Exponent bit result after base after Exponent after
13 1 3 4 6
6 0 3 1 3
3 1 3 1 1
1 1 3 1 0

The final result is 3.

Code Example

def modular_power(base: int, exponent: int, modulus: int) -> int:
    """Return base raised to exponent, reduced modulo modulus."""
    if modulus <= 0:
        raise ValueError("modulus must be positive")
    if exponent < 0:
        raise ValueError("exponent must be non-negative")

    result = 1 % modulus
    base %= modulus

    while exponent > 0:
        # Include the current power when the lowest exponent bit is set.
        if exponent & 1:
            result = (result * base) % modulus

        # Square the base and consume the current exponent bit.
        base = (base * base) % modulus
        exponent >>= 1

    return result


print(modular_power(3, 13, 5))  # 3

Common Pitfalls

  • Zero exponent: The function returns 1 % modulus; therefore, a modulus of 1 correctly produces 0.

  • Negative bases: Python’s % normalizes the result into the range 0 <= result < modulus.

  • Negative exponents: These are rejected because ordinary modular exponentiation requires a non-negative exponent.

  • Excessive intermediate values: Apply % modulus after every multiplication to keep values small.

  • Using ** for large exponents: base ** exponent can consume substantial memory. Use Python’s optimized pow(base, exponent, modulus) in production code.

  • Interview follow-ups: Common questions include using a left-to-right bit scan, handling a modulus of 1, explaining why the loop takes (O(log exponent)), and comparing the algorithm with repeated multiplication.

36

How do you XOR all integers in an inclusive range?

Prefix XOR computes the XOR of every integer in an inclusive range using a constant number of arithmetic and bitwise operations. The result is prefix(right) ^ prefix(left - 1), because XORing the shared prefix twice cancels it with x ^ x = 0.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Define the prefix XOR as:

P(n) = 0 ^ 1 ^ ... ^ n

Its value follows a repeating four-number pattern:

n % 4 P(n)
0 n
1 1
2 n + 1
3 0

Therefore, for nonnegative endpoints:

XOR(left..right) = P(right) ^ P(left - 1)

For the inclusive range [3, 7]:

  1. P(7) = 0, because 7 % 4 == 3.

  2. P(2) = 3, because 2 % 4 == 2.

  3. P(7) ^ P(2) = 0 ^ 3 = 3.

  4. Direct calculation confirms it: 3 ^ 4 ^ 5 ^ 6 ^ 7 = 3.

Bitwise Operators

Operator Meaning Example
& Bitwise AND: a bit is 1 only when both operands have 1 5 & 3 = 1
| Bitwise OR: a bit is 1 when either operand has 1 5 | 3 = 7
^ Bitwise XOR: a bit is 1 when the operands differ 5 ^ 3 = 6
~ Bitwise complement ~5 = -6
<< Shift bits left, multiplying by a power of two 5 << 1 = 10
>> Shift bits right, equivalent to floor division by a power of two 5 >> 1 = 2

Using format(x, "08b"), the bits of 5 are 0101 and the bits of 3 are 0011:

Bit position 5 3 5 ^ 3
3 0 0 0
2 1 0 1
1 0 1 1
0 1 1 0

The result is binary 0110, or decimal 6.

Handling Negative Integers

Python integers use infinite two’s complement, so ~x == -x - 1. For a negative range [left, right] we can map each negative x to ~(-x - 1). XORing an even number of complemented values cancels the complement; an odd number yields the complement of the XOR of the positive counterparts. The implementation splits the range at zero: - If both endpoints are negative, the positive counterparts run from -right - 1 to -left - 1. Their XOR is computed with the prefix function, then complemented if the number of negative terms (right - left + 1) is odd. - If the range crosses zero, the negative part [left, -1] has -left terms. Its XOR is the prefix XOR of -left - 1, complemented when -left is odd. This is then XORed with the prefix XOR of the non-negative part [0, right].

This matches Python’s native ^ behavior for all integers.

Complexity

  • Fixed-width interview model: Best, average and worst time are O(1) because the algorithm performs a constant number of arithmetic and bitwise operations. Auxiliary space is O(1).

  • Strict Python arbitrary-precision model: For b-bit endpoints, best, average and worst time are O(b) because operations on large integers process b bits. Auxiliary space is O(b) bits for a constant number of intermediate integers.

  • The input endpoints are not counted as auxiliary space, and no recursion stack is used.

Code Example

def _prefix_xor(end: int) -> int:
    """Return the XOR of integers from 0 through end (end >= 0)."""
    if end < 0:
        return 0
    remainder = end & 3
    if remainder == 0:
        return end
    if remainder == 1:
        return 1
    if remainder == 2:
        return end + 1
    return 0


def xor_range(left: int, right: int) -> int:
    """Return the XOR of all integers in the inclusive range [left, right]."""
    if left > right:
        raise ValueError("left must be less than or equal to right")

    if left >= 0:
        return _prefix_xor(right) ^ _prefix_xor(left - 1)

    if right < 0:
        # Both endpoints negative: map to positive range and complement if count is odd.
        count = right - left + 1
        pos_left = -right - 1
        pos_right = -left - 1
        pos_xor = _prefix_xor(pos_right) ^ _prefix_xor(pos_left - 1)
        return ~pos_xor if (count & 1) else pos_xor

    # left < 0 <= right: split into negative part [left, -1] and non-negative part [0, right].
    neg_count = -left
    neg_xor = _prefix_xor(-left - 1)
    if neg_count & 1:
        neg_xor = ~neg_xor
    return neg_xor ^ _prefix_xor(right)


print(xor_range(3, 7))   # 3
print(xor_range(-4, -2)) # -1
print(xor_range(-2, 1))  # 0

Common Pitfalls

  • Off-by-one errors: The range is inclusive, so the lower prefix ends at left - 1.

  • Empty range: left > right raises ValueError rather than returning an ambiguous result.

  • One-element range: xor_range(x, x) returns x.

  • Negative values: ~x is -x - 1, not merely the sign bit being flipped.

  • Operator confusion: ^ is XOR, while | is OR and & is AND.

  • Unnecessary materialization: Building list(range(left, right + 1)) takes O(n) time and space, defeating the constant-operation approach.

37

How do you generate all set subsets with bitmasks?

Use a bitmask to represent each subset: bit i indicates whether the element at index i is included. Enumerating every mask from 0 through 2^n - 1 generates all 2^n subsets exactly once.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Bitmasks Generate Subsets

Represent the set as a sequence of its distinct elements. If there are n elements, each subset corresponds to an n-bit mask.

  • Mask 0: no elements are selected.

  • Mask 1: only the first element is selected.

  • Mask 2: only the second element is selected.

  • Mask 3: the first two elements are selected.

  • Mask 2^n - 1: every element is selected.

For each mask, test each position with:

mask & (1 << index)

The result is nonzero exactly when that position is selected.

For elements [10, 20, 30] and mask 0b0101:

Index Element Bit test Selected?
0 10 0b0101 & 0b0001 = 0b0001 Yes
1 20 0b0101 & 0b0010 = 0b0000 No
2 30 0b0101 & 0b0100 = 0b0100 Yes

Thus, mask 0b0101 represents [10, 30].

Bitwise Operators

Python integers have arbitrary precision, so their bitwise operations are not limited to 32 or 64 bits.

Operator Meaning Example
& Bitwise AND; checks or combines set bits 0b1100 & 0b1010 = 0b1000
| Bitwise OR; sets a bit when either operand has it 0b1100 | 0b1010 = 0b1110
^ Bitwise XOR; sets a bit when the operands differ 0b1100 ^ 0b1010 = 0b0110
~ Bitwise NOT In Python, ~x == -x - 1, so ~0b1010 == -11
<< Shift bits left, multiplying by two per position 0b0010 << 2 == 0b1000
>> Shift bits right 0b1000 >> 2 == 0b0010

For fixed-width binary display, format(0b1010, "08b") returns "00001010". To inspect the low 32 bits of a Python integer, use & 0xFFFFFFFF; these bits form the unsigned representation of the corresponding 32-bit two’s-complement bit pattern, while Python itself does not overflow.

Complexity

For n distinct elements, the output contains 2^n subsets and n × 2^(n-1) total element memberships.

Approach Time Space When to use
Recursive include/exclude O(n × 2^n) O(n) stack plus O(n × 2^n) output When recursive decomposition is useful
Bitmask enumeration O(n × 2^n) O(n) auxiliary plus O(n × 2^n) output When an explicit list of all subsets is required
  • Best, average, and worst-case time: O(n × 2^n) for every case because the algorithm tests all n positions for every mask.

  • Auxiliary space: O(n) for the copied element list and current subset.

  • Output space: O(n × 2^n).

  • Recursion stack: O(1) for the iterative implementation.

  • The original input is not counted in auxiliary space; the copied elements list is.

Code Example

from collections.abc import Hashable, Iterable
from typing import TypeVar

T = TypeVar("T", bound=Hashable)


def generate_subsets(values: Iterable[T]) -> list[list[T]]:
    """Return all distinct subsets, preserving the input encounter order."""
    # Deduplicate while preserving the first occurrence of each element.
    elements = list(dict.fromkeys(values))
    subset_count = 1 << len(elements)

    subsets: list[list[T]] = []

    for mask in range(subset_count):
        subset: list[T] = []

        for index, element in enumerate(elements):
            if mask & (1 << index):
                subset.append(element)

        subsets.append(subset)

    return subsets


print(generate_subsets([1, 2, 3]))
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

For an actual Python set, iteration order is unspecified, so convert it to an ordered sequence first if deterministic output is important.

Common Pitfalls

  • Wrong bit meaning: 1 << index selects an element by its position; it does not inspect the element’s own binary value.

  • Empty input: The function correctly returns [[]], representing the empty subset.

  • Single element: For [x], the function returns [[], [x]].

  • Duplicates: Actual sets cannot contain duplicates; the function also removes duplicates from other iterables.

  • Negative values: Negative elements work normally because masks represent positions, not element values.

  • Already sorted input: The function preserves the input encounter order, so an already sorted sequence remains sorted.

  • Fixed-width overflow: Python has arbitrary-precision integers, but 1 << n can overflow a 32- or 64-bit type in other languages.

  • NOT operator trap: ~x is -x - 1 in Python, not merely the reversal of a fixed-width representation.

  • Memory usage: Materializing all subsets requires O(n × 2^n) space. A generator or Gray-code traversal can reduce peak memory when only one subset is needed at a time.

38

How do you check whether an integer's binary representation is a palindrome?

A binary palindrome reads identically from both ends when the integer’s canonical binary digits are considered without leading zeros. You can detect one by reversing the significant bits with bitwise operations and comparing the reversed value with the original.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

For a nonnegative integer:

  1. Save the original value.

  2. Use number & 1 to extract its least significant bit.

  3. Shift reversed_bits left and append that bit using |.

  4. Shift number right to process the next bit.

  5. Compare the original and reversed values.

For example, 10 has binary representation 1010:

Step Current value Extracted bit Reversed bits
Initial 00001010 — 00000000
1 00001010 0 00000000
2 00000101 1 00000001
3 00000010 0 00000010
4 00000001 1 00000101

The reversed significant bits are 0101, so 10 is not a binary palindrome.

Python Bitwise Operators

Operator Purpose Example
& Bitwise AND; selects bits present in both operands format(13 & 10, '08b') is 00001000
| Bitwise OR; combines set bits format(13 | 10, '08b') is 00001111
^ Bitwise XOR; sets bits present in exactly one operand format(13 ^ 10, '08b') is 00000101
~ Bitwise NOT In Python, ~13 == -14; its 8-bit two’s-complement representation is 11110010
<< Shifts bits left, multiplying by two format(13 << 1, '08b') is 00011010
>> Shifts bits right, dividing by two format(13 >> 1, '08b') is 00000110

Useful related tricks include:

  • x & (x - 1) clears the lowest set bit.

  • x & -x isolates the lowest set bit.

  • x ^ x is always 0 for one integer.

  • x > 0 and (x & (x - 1)) == 0 tests whether x is a power of two.

  • x.bit_count() counts set bits in Python 3.10 and later.

Complexity and Edge Cases

Let b be the number of significant bits in the integer.

Approach Time Auxiliary space When to use
Convert to a binary string O(b) O(b) Simplicity is more important
Reverse bits numerically O(b) integer-operation steps; O(b²) under strict Python arbitrary-precision accounting O(1) integer variables, or O(b) bits in strict bit-space accounting Bit-manipulation practice
  • Best, average and worst time: The string approach is O(b) in every case. Numeric reversal performs exactly O(b) iterations, giving O(b) time when integer operations are treated as constant-time. Because Python integers are arbitrary precision and each shift processes the integer’s current digits, the numeric implementation requires O(b²) bit/digit work under strict Python accounting.

  • Auxiliary space: Numeric reversal uses O(1) integer variables in the standard word-RAM model, excluding the input and with no recursion stack. Under strict bit-space accounting, those variables require O(b) bits.

  • Zero and one-bit values: Both 0 and 1 are palindromes.

  • Negative values: The implementation rejects them because the algorithm concerns unsigned binary digits.

  • Empty input, duplicate values, sorted order, disconnected graphs and cycles are not applicable to this scalar-integer problem.

Code Example

def is_binary_palindrome(number: int) -> bool:
    """Return whether number's canonical binary representation is a palindrome."""
    if number < 0:
        return False

    original = number
    reversed_bits = 0

    while number > 0:
        reversed_bits = (reversed_bits << 1) | (number & 1)
        number >>= 1

    return original == reversed_bits


print(is_binary_palindrome(9))   # True: binary 1001
print(is_binary_palindrome(10))  # False: binary 1010

Common Pitfalls and Interview Tips

  • Do not use fixed-width padding to decide whether the representation is a palindrome. For example, 1 is a palindrome as 1, but padded to eight bits it becomes 00000001.

  • Use parentheses around bitwise expressions before comparisons to avoid precedence mistakes.

  • Python integers are arbitrary-precision and do not overflow. Consequently, Python’s ~x equals -x - 1; fixed-width two’s-complement behavior requires an explicit mask such as & 0xFFFFFFFF.

  • A common interviewer follow-up is to solve the same problem using bin(number)[2:]; it has O(b) time but also O(b) string space.

39

How can two integers be compared using bit manipulation without comparison operators?

Comparison-free minimum and maximum can be computed by creating a mask that selects the smaller or larger operand. In Python 3.12, the implementation uses integer bit operations and an arithmetic right shift, without <, >, <=, or >=.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For two integers a and b:

  1. Compute difference = a - b.

  2. Choose a shift width large enough to contain the difference.

  3. Shift the difference right arithmetically:

  4. A negative difference becomes -1 (all bits set in two’s complement).

  5. A non‑negative difference becomes 0 (no bits set).

  6. Use the resulting mask to select the values:

  7. When mask == -1 (meaning a < b), select a as the minimum and b as the maximum.

  8. When mask == 0 (meaning a >= b), select b as the minimum and a as the maximum.

Python integers have arbitrary precision, so subtraction and shifts do not overflow.

Step-by-Step Example

Trace the algorithm for a = 3, b = 7:

  1. magnitude = abs(3) | abs(7) = 3 | 7 = 7 → bit_length = 3 → width = 4.

  2. difference = 3 - 7 = -4.

  3. mask = -4 >> 4 = -1 (binary ...1111).

  4. minimum = (3 & -1) | (7 & 0) = 3.

  5. maximum = (7 & -1) | (3 & 0) = 7. Result: (3, 7).

Bitwise Operators

The relevant operators are:

Operator Meaning Example
x & y Bitwise AND 12 & 10 → 8 (00001000)
x | y Bitwise OR 12 | 10 → 14 (00001110)
x ^ y Bitwise XOR 12 ^ 10 → 6 (00000110)
~x Bitwise NOT ~10 → -11, because Python uses ~x == -x - 1
x << n Shift bits left by n positions 3 << 2 → 12 (00001100)
x >> n Arithmetic right shift -4 >> 2 → -1

For example, format(12, "08b") is 00001100, while format(10, "08b") is 00001010.

Bit position 12 10 12 & 10 12 | 10 12 ^ 10
3 1 1 1 1 0
2 1 0 0 1 1
1 0 1 0 1 1
0 0 0 0 0 0

The key trick is that 0 is a mask selecting nothing, while -1 is a mask selecting every bit.

Complexity

  • Best, average, and worst-case time: O(1) for fixed-width integers, since the algorithm performs a constant number of arithmetic and bitwise operations.

  • Auxiliary space: O(1) for fixed-width integers.

  • With Python’s arbitrary-precision integers and inputs containing k bits, the operations take O(k) time and O(k) auxiliary space for intermediate integers. The input integers themselves are not counted as auxiliary space.

Code Example

def min_max_without_comparisons(a: int, b: int) -> tuple[int, int]:
    """Return the minimum and maximum of two integers without comparisons."""
    magnitude = abs(a) | abs(b)
    width = magnitude.bit_length() + 1

    difference = a - b
    mask = difference >> width

    minimum = (a & mask) | (b & ~mask)
    maximum = (b & mask) | (a & ~mask)

    return minimum, maximum


print(min_max_without_comparisons(7, 3))   # (3, 7)
print(min_max_without_comparisons(3, 7))   # (3, 7)
print(min_max_without_comparisons(-5, 2))  # (-5, 2)
print(min_max_without_comparisons(0, 0))   # (0, 0)

Common Pitfalls

  • Python ~ is not a fixed-width complement: ~x equals -x - 1. Masking with -1 is useful because it preserves every bit of a Python integer.

  • Right shift semantics: Python uses arithmetic right shift, so negative values shift toward negative infinity and -1 remains -1.

  • Choose a sufficient width: The implementation uses the bit length of the larger magnitude plus one so the difference cannot be mistaken for the opposite sign.

  • Fixed-width languages: In C or Java, ensure intermediate arithmetic has enough bits for a - b; otherwise, signed overflow can invalidate the mask.

  • Edge cases: Equal values return two identical results, zero and negative values work normally, and no empty-input or single-element handling is needed because the function always receives exactly two integers.

40

How can bit manipulation detect opposite signs in two integers?

Sign-bit XOR detects opposite signs: in two’s-complement representation, XORing two integers with different sign bits produces a negative result. Zero must be handled separately because it has neither a positive nor a negative sign.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • A signed two’s-complement integer’s highest bit is its sign bit: 0 means nonnegative and 1 means negative.

  • XOR (^) produces 1 when the corresponding bits differ.

  • Therefore, if the inputs have different sign bits, the XOR result has a sign bit of 1, making it negative.

  • If both inputs have the same sign bit, the XOR result is nonnegative.

For example, using four-bit two’s-complement values:

Bit 3 2 1 0
5 (0101) 0 1 0 1
-3 (1101) 1 1 0 1
5 ^ -3 (1000) 1 0 0 0

The sign bits differ, so the result is negative. These values can be displayed with:

format(5 & 0xF, "04b")       # 0101
format(-3 & 0xF, "04b")      # 1101
format((5 & 0xF) ^ (-3 & 0xF), "04b")  # 1000

Bitwise Operators

Operator Purpose Example
& Bitwise AND; commonly extracts or tests bits 5 & 3 == 1
| Bitwise OR; sets bits when either operand has them set 5 | 3 == 7
^ Bitwise XOR; sets bits when the operands differ 5 ^ 3 == 6
~ Bitwise NOT; in Python, ~x == -x - 1 ~5 == -6
<< Shifts bits left, multiplying by a power of two 1 << 3 == 8
>> Shifts bits right; behavior for negative signed values can vary by language 8 >> 2 == 2

Python integers have arbitrary precision, so they do not overflow. Unlike fixed-width languages, Python conceptually represents negative integers with an unlimited sequence of leading 1 bits. Consequently, after excluding zero, (left ^ right) < 0 correctly identifies inputs with opposite signs.

Code Example

def have_opposite_signs(left: int, right: int) -> bool:
    """Return whether two integers have opposite nonzero signs."""
    if left == 0 or right == 0:
        return False

    return (left ^ right) < 0


print(have_opposite_signs(5, -3))  # True

For fixed-width signed values, an explicit sign-bit test can instead use a mask. For signed 32-bit inputs, that would be:

((left ^ right) & 0x80000000) != 0

The mask selects bit 31, the 32-bit sign bit.

Complexity

Let n be the maximum bit length of the two integers.

  • Fixed-width integers: best, average and worst time are O(1) because the XOR operates on one machine word.

  • Arbitrary-precision integers: best, average and worst time are O(n) because Python must process the integer’s digit representation.

  • Auxiliary space: O(1) for fixed-width integers and O(n) for the temporary XOR result with arbitrary-precision integers.

  • These space bounds exclude the input values themselves. The recursion stack is O(1) because the algorithm is not recursive.

Common Pitfalls

  • Handling zero incorrectly: 0 has no sign. A test such as (0 ^ -3) < 0 evaluates to True, so explicitly return False when either operand is zero.

  • Assuming fixed-width overflow rules in Python: Python integers do not overflow, and ~x equals -x - 1.

  • Confusing XOR with equality: x ^ y == 0 only when x == y; it does not indicate same sign. Two different values with the same sign will have a non-zero XOR result (but non-negative).

  • Using signed right shifts across languages: The behavior of >> for negative values can differ. The XOR sign-bit technique avoids shifts.

  • Common follow-up questions: Interviewers may ask for an explicit 32-bit mask, how zero should be treated, or why the XOR result’s sign bit represents whether the original signs differed.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 40 Bit Manipulation answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects