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 answerHide 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 & -xisolates the lowest set bit. -
x ^ xis always0for one number. -
x > 0 and (x & (x - 1)) == 0checks whetherxis 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, subtract2**32when it is at least2**31. -
Python NOT behavior:
~xequals-x - 1, so~12is-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:
0is not a power of two, so thex > 0condition is necessary. -
Bit versus byte: A bit is one binary digit; a byte contains 8 bits.