You can also find all 40 answers here 👉 Devinterview.io - Bit Manipulation
The term "bit" is a portmanteau of binary digit. It represents the fundamental unit of information in Shannon information theory and digital computing. A bit exists in one of two mutually exclusive states: 0 or 1, mapping to the Boolean values {False, True}.
Computers utilize a base-2 (binary) positional notation system. Unlike the human base-10 (decimal) system, which uses ten digits (0-9), binary scales by powers of 2.
- Bit: A single
2^0unit. - Nibble: 4 bits (
2^4 = 16possible values,0to15). Often represented as a single Hexadecimal digit (0x0 ... 0xF). - Byte (Octet): 8 bits (
2^8 = 256possible values,0to255). In 2026, the byte remains the smallest addressable unit of memory in standard architectures (x86_64,ARMv9).
Example: The decimal number 5 is represented as 00000101 in binary, which equals (1 x 2^2) + (0 x 2^1) + (1 x 2^0).
Bit manipulation involves direct algorithmic operations on bits via bitwise operators. These operations are executed very efficiently and are useful for tasks like compression, encryption, and protocol handling.
Logical AND Example: 42 & 12 = 8.
In binary, 00101010 & 00001100 = 00001000.
In modern systems, integer bit-width is determined by the language runtime and architecture:
- Fixed-Width Integers: Common in C++23/Rust, defined as
int32_tori64. A signed 64-bit integer uses Two's Complement representation, spanning the range[-2^63, 2^63 - 1]. - Arbitrary Precision: In Python 3.14+, integers are objects that dynamically allocate memory. They do not "overflow" in the traditional sense, as they scale to use as many bits as required by the available RAM.
While 32-bit systems are legacy, 2026 hardware is predominantly 64-bit. A 64-bit CPU features registers and an Address Bus capable of processing 64-bit words natively.
- Word Size: The natural data size handled by the CPU (usually 64 bits).
- SIMD (Single Instruction, Multiple Data): Modern processors use 256-bit (AVX-2) or 512-bit (AVX-512/AMX) registers to manipulate multiple bits or integers in parallel.
- Memory Addressing: 64 bits allow for a theoretical
2^64bytes of addressable memory (16exabytes), though practical limits are lower.
A byte is the standard unit of digital information, typically consisting of 8 bits. In modern architecture, it is formally defined as an octet. It represents
A byte uses a base-2 (binary) positional system. Each bit position
| Bit Position ( |
Power of 2 ( |
Decimal Value (Place Value) |
|---|---|---|
| 7 (MSB) | 128 | |
| 6 | 64 | |
| 5 | 32 | |
| 4 | 16 | |
| 3 | 8 | |
| 2 | 4 | |
| 1 | 2 | |
| 0 (LSB) | 1 |
To convert a binary representation to a decimal value, multiply each bit by its positional weight and add the results. In other words, each bit b_i contributes b_i * 2^i to the final decimal number.
For a full byte with all bits set to 1, the value is:
1*2^7 + 1*2^6 + 1*2^5 + 1*2^4 + 1*2^3 + 1*2^2 + 1*2^1 + 1*2^0 = 255
While string parsing is common in pedagogy, production-grade Bit Manipulation utilizes bitwise operators or built-in bytearray types for memory efficiency and
def byte_to_decimal(bit_string: str) -> int:
"""
Converts a binary string to decimal using Python 3.14+
builtin integer evaluation.
"""
if len(bit_string) != 8:
raise ValueError("Input must be an 8-bit string (octet).")
# Use base-2 conversion; O(n) where n is string length
return int(bit_string, 2)
def bit_weight_sum(bits: list[int]) -> int:
"""
Manual bitwise reconstruction using the Left-Shift operator.
Efficient for stream processing.
"""
decimal_val: int = 0
for bit in bits:
# Shift existing value left and perform bitwise OR
decimal_val = (decimal_val << 1) | bit
return decimal_val
# Industry Standard: Handling raw byte objects
raw_data: bytes = b'\xff' # Hex for 255
decimal_output: int = int.from_bytes(raw_data, byteorder='big')
print(f"Decimal Output: {decimal_output}") # Output: 255In 2026 systems programming, bytes are often handled within SIMD registers (Single Instruction, Multiple Data) where 16, 32, or 64 bytes are processed in parallel (
Bitwise operations manipulate data at the level of individual bits (0 and 1). In modern computing, these operations are performed directly by the Arithmetic Logic Unit (ALU) within the CPU, making them significantly faster than high-level arithmetic. In Python 3.14+, integers are treated as arbitrary-precision objects, but bitwise logic continues to operate on their underlying Two's Complement binary representation.
-
Performance: Bitwise operations execute in a single CPU cycle (
$O(1)$ complexity). They bypass the overhead of complex arithmetic circuits. - Memory Optimization: Pack multiple boolean states (flags) into a single integer. For example, a 64-bit integer can store 64 distinct boolean values, reducing memory footprint by up to 8x compared to an array of booleans.
- Hardware Interfacing: Essential for writing drivers, managing registers, and communicating with hardware via protocols like I2C or SPI.
- Algorithmic Efficiency: Critical in tasks like Cryptographic Hashing, Checksums (CRC32), and SIMD (Single Instruction, Multiple Data) processing.
- AND (
&): Returns1if both bits are1. Used for Masking (extracting specific bits).- Example:
5 & 3 = 1, because0101 & 0011 = 0001.
- Example:
- OR (
|): Returns1if at least one bit is1. Used for Setting specific bits.- Example:
5 | 3 = 7, because0101 | 0011 = 0111.
- Example:
- XOR (
^): Returns1only if the bits differ. Used for Toggling and parity checks.- Example:
5 ^ 3 = 6, because0101 ^ 0011 = 0110.
- Example:
- NOT (
~): Inverts all bits. In Two's Complement,~xis equivalent to-(x + 1).- Example:
~5 = -6.
- Example:
-
Left Shift (
<<): Shifts bits to the left, padding with zeros. Effectively multiplies by$2^n$ .- Formula:
$x \ll n = x \cdot 2^n$ . - Example:
$5 \ll 2 = 20$ .
- Formula:
-
Right Shift (
>>): Shifts bits to the right. For positive numbers, this is equivalent to floor division by$2^n$ .- Formula:
$x \gg n = \lfloor \frac{x}{2^n} \rfloor$ . - Example:
$5 \gg 2 = 1$ .
- Formula:
-
Unsigned Right Shift (
>>>): (Specific to Java/JavaScript/C++). Python does not have a native>>>because it uses arbitrary-precision integers. To simulate a 32-bit unsigned shift in Python:(n & 0xFFFFFFFF) >> shift.
-
Two's Complement: The standard for representing signed integers. To negate a number: invert all bits and add 1.
- Formula:
$-x = (\sim x) + 1$ .
- Formula:
-
Bit Population Count: In Python 3.14+, use
int.bit_count()to calculate the Hamming Weight (number of set bits).
- Bloom Filters: Using hash results as bit indices to provide space-efficient membership queries.
- Permissions (RBAC): Storing Read/Write/Execute permissions as
0b111(7). - Graphics: Manipulating ARGB color channels where each channel occupies 8 bits of a 32-bit integer.
Using enum.IntFlag is the 2026 standard for type-safe bitwise flag manipulation.
from enum import IntFlag, auto
class FilePermissions(IntFlag):
READ = auto() # 0b0001
WRITE = auto() # 0b0010
EXECUTE = auto() # 0b0100
DELETE = auto() # 0b1000
# Assign permissions using OR
current_perms = FilePermissions.READ | FilePermissions.WRITE
# Check permissions using AND
is_executable = bool(current_perms & FilePermissions.EXECUTE)
# Toggle a permission using XOR
current_perms ^= FilePermissions.DELETE
print(f"Permissions: {current_perms.name} | Binary: {bin(current_perms)}")
# Output: Permissions: READ|WRITE|DELETE | Binary: 0b1011
# High-performance bit count (Python 3.10+)
print(f"Active flags count: {current_perms.bit_count()}") Bitwise operators (
- Huffman Coding & Variable-Length Codes: Modern compression (e.g., Zstandard, Brotli) uses bitwise shifts to append variable-bit-length symbols into a byte-aligned stream.
- Bit-Packing: Storing multiple low-precision values (e.g., three 10-bit color channels) into a single 32-bit integer to minimize cache misses and bus traffic.
- Symmetric Primitives: Algorithms like AES and ChaCha20 rely on XOR ($ \oplus $) and bitwise rotations to achieve "confusion and diffusion."
- Post-Quantum Cryptography (PQC): Lattice-based schemes (e.g., CRYSTALS-Kyber) utilize bit-masking for polynomial coefficient reduction and efficient error correction.
- CIDR Subnetting: IPv4 and IPv6 routing use the bitwise AND operator to determine network prefixes:
subnet = ip & mask. - Checksums & CRC: Cyclic Redundancy Checks (CRC) use bitwise XOR and shifts to detect data corruption in high-speed ethernet frames.
- Register-Level Access: Interfacing with hardware involves Read-Modify-Write cycles.
- Set bit:
register |= (1 << n) - Clear bit:
register &= ~(1 << n) - Toggle bit:
register ^= (1 << n)
- Set bit:
- Memory-Mapped I/O (MMIO): Direct manipulation of peripheral control registers via bit-masks.
-
Power of Two Check: Determining if an integer
nis a power of two inO(1):n > 0 and (n & (n - 1)) == 0. -
Bitsets: Replacing boolean arrays with bit-fields to reduce memory usage by a factor of
$8 \times$ .
- SIMD Operations: Single Instruction, Multiple Data (SIMD) units use bitwise masks to apply transformations to multiple pixels simultaneously.
-
Alpha Blending: Optimized integer math uses shifts (
$\gg$ ) instead of divisions (e.g., dividing by 256 via$\gg 8$ ) for real-time rendering.
-
Parity Bit Calculation: Used in serial communication to detect single-bit errors. Python 3.14+ provides
int.bit_count()for hardware-accelerated population count ($Popcount$ ). -
Bloom Filters: Uses bitwise
$OR$ and hash-generated indices to provide probabilistic membership testing in large datasets.
The previous RLE example was architecturally inconsistent as it used string manipulation. The following Python 3.14+ example demonstrates Bitmasking for efficient system state management.
from enum import IntFlag
class SystemState(IntFlag):
"""Represents system flags using Bit-Fields."""
IDLE = 0
READ_PERMISSION = 1 << 0 # 0001
WRITE_PERMISSION = 1 << 1 # 0010
EXECUTE_PERMISSION = 1 << 2 # 0100
ENCRYPTED = 1 << 3 # 1000
def audit_permissions(current_state: int):
# bit_count() available since Python 3.10+, optimized in 3.14
active_flags = current_state.bit_count()
# Check for specific flag using bitwise AND
can_write = bool(current_state & SystemState.WRITE_PERMISSION)
# Toggle a flag using XOR
new_state = current_state ^ SystemState.ENCRYPTED
return {
"hex_representation": hex(current_state),
"active_count": active_flags,
"write_access": can_write,
"toggled_encryption": hex(new_state)
}
# Simulation: User has Read and Write access (0001 | 0010 = 0011)
state = SystemState.READ_PERMISSION | SystemState.WRITE_PERMISSION
results = audit_permissions(state)
print(f"System State Analysis: {results}")
# Bitwise Power of Two Verification
is_power_of_two = lambda n: n > 0 and (n & (n - 1)) == 0
print(f"Is 1024 power of 2? {is_power_of_two(1024)}")-
Time Complexity: All bitwise operations (
$AND, OR, XOR, \ll, \gg$ ) are$O(1)$ at the processor level. -
Space Complexity:
$O(1)$ per flag-set, utilizing the minimum number of bits required to represent the integer ($log_2(n)$).
The bitwise AND (&) is a fundamental binary operation executed at the hardware level by the Arithmetic Logic Unit (ALU). It compares the binary representation of two integers bit by bit.
- The resulting bit is
1only if both corresponding input bits are1. - Otherwise, the resulting bit is
0.
In fixed-width machine arithmetic, this is typically treated as an O(1) operation and is widely used in bitmasking, cryptography, and low-level systems code.
To determine if a decimal integer is odd or even, inspect the Least Significant Bit (LSB), which is the rightmost bit in the binary representation.
- If the LSB is
1, the number is odd. - If the LSB is
0, the number is even.
This works because every higher bit represents an even power-of-two contribution, so parity depends only on the 2^0 place.
For an integer n, checking n & 1 isolates the least significant bit.
- If
n & 1 == 0, the number is even. - If
n & 1 == 1, the number is odd.
Modern Python utilizes arbitrary-precision integers, but the bitwise logic remains consistent and efficient for parity checks.
def is_odd(n: int) -> bool:
"""
Determines parity using the bitwise AND operator.
Complexity: O(1)
"""
return (n & 1) == 1
def is_even(n: int) -> bool:
"""
Determines parity by checking if the LSB is zero.
"""
return (n & 1) == 0While n % 2 != 0 is the standard high-level approach, n & 1 is the canonical low-level implementation. In 2026, modern JIT compilers (like PyPy or GraalPy) and ahead-of-time (AOT) compilers optimize the modulo operator into a bitwise AND for constant divisors of 2^k automatically.
Explore all 40 answers here 👉 Devinterview.io - Bit Manipulation