Hyppää sisältöön

Ei vielä käännetty

Tätä sivua ei ole vielä käännetty suomeksi, joten se näytetään englanniksi. Auta kääntämään

bin() Function Complexity

The bin() function returns the binary representation of an integer.

Complexity Analysis

Case Time Space Notes
Convert integer O(log n) O(log n) n = integer value; log n = number of bits
Negative integer O(log n) O(log n) Adds '-0b' prefix
Large integer O(b) O(b) b = number of bits = log₂(n)

Note: The complexity is O(log n) where n is the numeric value, which equals the number of bits needed to represent the number.

Basic Usage

Decimal to Binary

# O(log n) - where n = integer value
bin(0)      # '0b0'
bin(1)      # '0b1'
bin(2)      # '0b10'
bin(3)      # '0b11'
bin(8)      # '0b1000'
bin(255)    # '0b11111111'

Negative Numbers

# O(log n) - shows magnitude with minus
bin(-1)     # '-0b1'
bin(-8)     # '-0b1000'
bin(-255)   # '-0b11111111'

Large Integers

# O(log n) - number of binary digits
bin(2**10)    # '0b10000000000'
bin(2**32)    # '0b100000000000000000000000000000000'

# Arbitrary precision
big = 2**100
bin(big)  # O(100) - 100+ binary digits

Complexity Details

Logarithmic Time

Conversion time grows with the number of bits:

# Small number - few bits
bin(3)      # '0b11' - 2 bits, O(log 3) = O(2)

# Large number - many bits
bin(2**64 - 1)  # 64 bits
                # O(log(2**64)) = O(64)

# Relationship: binary digits = log₂(n)
import math
value = 255
digits = len(bin(value)) - 2  # Subtract '0b'
assert digits == value.bit_length()

Common Patterns

Bit Manipulation

# O(log n) - understand bit patterns
x = 42
print(bin(x))  # '0b101010'

# Check individual bits
def has_bit_set(value, bit_pos):
    return bool(value & (1 << bit_pos))

value = 0b1010  # 10 in decimal
print(has_bit_set(value, 0))  # False (bit 0)
print(has_bit_set(value, 1))  # True (bit 1)

Debugging Bitwise Operations

# O(log n) - show results clearly
a = 0b1100
b = 0b1010

print(f"a = {bin(a)}")           # a = 0b1100
print(f"b = {bin(b)}")           # b = 0b1010
print(f"a & b = {bin(a & b)}")   # a & b = 0b1000
print(f"a | b = {bin(a | b)}")   # a | b = 0b1110
print(f"a ^ b = {bin(a ^ b)}")   # a ^ b = 0b0110
print(f"~a = {bin(~a)}")         # ~a = -0b1101

Binary String to Integer

# O(log n) - parse binary string
binary_str = "0b1010"
value = int(binary_str, 2)  # O(log n)
assert value == 10

# Without prefix
value = int("1010", 2)  # Also O(log n)
assert value == 10

Bit Manipulation Operations

# All O(1) in Python (fixed size, usually)
x = 0b1100  # 12
y = 0b1010  # 10

# Bitwise AND
result = x & y  # 0b1000 (8)
print(bin(result))  # '0b1000'

# Bitwise OR
result = x | y  # 0b1110 (14)
print(bin(result))  # '0b1110'

# Bitwise XOR
result = x ^ y  # 0b0110 (6)
print(bin(result))  # '0b110'

# Bitwise NOT (inverts all bits)
result = ~x     # -(13) due to two's complement
print(bin(result))  # '-0b1101'

# Left shift
result = x << 2  # 0b110000 (48)
print(bin(result))  # '0b110000'

# Right shift
result = x >> 1  # 0b110 (6)
print(bin(result))  # '0b110'

Performance Patterns

Batch Conversion

# O(n * log m) - n numbers, each ~m value
numbers = list(range(100))
binary_values = [bin(n) for n in numbers]
# O(100 * log 100)

# vs direct method
binary_values = [f"{n:b}" for n in numbers]
# Similar, might be slightly faster with format

Counting Set Bits

# O(log n) - using bin()
def count_bits_bin(value):
    return bin(value).count('1')

# Better - O(1) with bit_count()
def count_bits_optimal(value):
    return value.bit_count()  # Python 3.10+

# Both give same result, bit_count() is faster
assert count_bits_bin(0b101010) == count_bits_optimal(0b101010)

Practical Examples

Permission Flags

# O(log n) - display permission bits
READ = 0b100
WRITE = 0b010
EXECUTE = 0b001

permissions = READ | WRITE  # 0b110 (read + write)
print(bin(permissions))      # '0b110'

# Check if permission set
has_read = bool(permissions & READ)
has_write = bool(permissions & WRITE)
has_execute = bool(permissions & EXECUTE)

IP Address Manipulation

# O(log n) - work with IP octets
ip = "192.168.1.1"
octets = [int(x) for x in ip.split('.')]

# Show first octet in binary
print(bin(octets[0]))  # '0b11000000' (192)

# Network mask
mask = 0b11111111_11111111_11111111_00000000  # /24
print(bin(mask))

Set Operations with Bits

# O(log n) - use integers as efficient sets
SET_SIZE = 8  # Can represent 0-7

# Add elements (set bits)
my_set = 0  # Empty set
my_set |= (1 << 3)  # Add 3
my_set |= (1 << 5)  # Add 5

print(bin(my_set))  # '0b101000'

# Check membership
print(bool(my_set & (1 << 3)))  # True (has 3)
print(bool(my_set & (1 << 2)))  # False (no 2)

# Remove element (clear bit)
my_set &= ~(1 << 3)
print(bin(my_set))  # '0b100000'

Best Practices

✅ Do:

  • Use bin() for debugging bitwise operations
  • Use format(value, 'b') if you don't need '0b' prefix
  • Use bit_length() or bit_count() for counting
  • Use int(binary_str, 2) to parse binary

❌ Avoid:

  • Using bin() for very frequent operations (cache result)
  • Assuming binary operations are faster than regular ops
  • Building binary from decimal without understanding conversion
  • Forgetting the '0b' prefix when parsing with int()

Version Notes

  • Python 2.x: Works with int and long
  • Python 3.x: Works with arbitrary precision integers
  • Python 3.10+: Added int.bit_count() for bit counting
  • All versions: Returns string with '0b' prefix