tessl/pypi-gmpy2
Multiple-precision arithmetic library providing fast GMP, MPFR, and MPC interfaces for Python
—
Pending
bit-operations.mddocs/
Bit Operations
gmpy2 provides comprehensive bit manipulation operations for integer types (mpz and xmpz). These operations are highly optimized and work efficiently with arbitrarily large integers.
Capabilities
Basic Bit Operations
Fundamental bit manipulation functions for setting, clearing, and testing individual bits.
def bit_set(x, n):
"""
Set bit n in integer x.
Args:
x: Integer value (mpz, xmpz, or int)
n: Bit position (0-based, 0 is least significant)
Returns:
New integer with bit n set to 1
Note:
For mpz, returns new object. For xmpz methods, modifies in place.
"""
def bit_clear(x, n):
"""
Clear bit n in integer x.
Args:
x: Integer value
n: Bit position (0-based)
Returns:
New integer with bit n set to 0
"""
def bit_flip(x, n):
"""
Flip (toggle) bit n in integer x.
Args:
x: Integer value
n: Bit position (0-based)
Returns:
New integer with bit n flipped
"""
def bit_test(x, n):
"""
Test if bit n is set in integer x.
Args:
x: Integer value
n: Bit position (0-based)
Returns:
bool: True if bit n is 1, False if bit n is 0
"""Bit Counting and Scanning
Functions for analyzing bit patterns and finding specific bits.
def bit_count(x):
"""
Count the number of set bits (population count).
Args:
x: Integer value
Returns:
int: Number of bits set to 1
Note:
Also available as popcount(x)
"""
def popcount(x):
"""
Population count (alias for bit_count).
Args:
x: Integer value
Returns:
int: Number of bits set to 1
"""
def bit_length(x):
"""
Number of bits needed to represent the integer.
Args:
x: Integer value
Returns:
int: Number of bits in binary representation (excluding sign)
Note:
For negative numbers, returns length of absolute value
"""
def bit_scan0(x, start=0):
"""
Find the first clear bit (0) starting from a position.
Args:
x: Integer value
start: Starting bit position (default 0)
Returns:
int: Position of first clear bit >= start, or None if none found
"""
def bit_scan1(x, start=0):
"""
Find the first set bit (1) starting from a position.
Args:
x: Integer value
start: Starting bit position (default 0)
Returns:
int: Position of first set bit >= start, or None if none found
"""Bit Mask Operations
Functions for creating and working with bit masks.
def bit_mask(n):
"""
Create a mask with n bits set to 1.
Args:
n: Number of bits to set
Returns:
mpz: Integer with lowest n bits set to 1
Example:
bit_mask(4) returns 15 (binary: 1111)
"""
def xbit_mask(n):
"""
Create an xmpz mask with n bits set to 1.
Args:
n: Number of bits to set
Returns:
xmpz: Mutable integer with lowest n bits set to 1
"""Hamming Distance
Function for computing bit difference between integers.
def hamdist(x, y):
"""
Compute Hamming distance between two integers.
Args:
x, y: Integer values
Returns:
int: Number of bit positions where x and y differ
Note:
Equivalent to popcount(x ^ y)
"""Integer Root Operations with Remainder
Functions for integer square roots and higher roots with bit-based implementation.
def isqrt(x):
"""
Integer square root.
Args:
x: Non-negative integer
Returns:
mpz: Largest integer n such that n² <= x
"""
def isqrt_rem(x):
"""
Integer square root with remainder.
Args:
x: Non-negative integer
Returns:
tuple: (root, remainder) where x = root² + remainder
"""
def iroot(x, n):
"""
Integer nth root.
Args:
x: Integer value
n: Root degree (positive integer)
Returns:
tuple: (root, is_exact) where is_exact indicates if root is exact
"""
def iroot_rem(x, n):
"""
Integer nth root with remainder.
Args:
x: Integer value
n: Root degree (positive integer)
Returns:
tuple: (root, remainder) where x = root^n + remainder
"""Advanced Bit Iteration (xmpz only)
Advanced bit iteration methods available for mutable integers.
# Note: These are methods of xmpz class, shown for completeness
class xmpz:
def iter_bits(self, start=0, stop=-1):
"""
Iterator over all bit positions (both set and clear).
Args:
start: Starting bit position (default 0)
stop: Ending bit position (default -1 for no limit)
Yields:
int: Bit positions in order
"""
def iter_set(self, start=0, stop=-1):
"""
Iterator over positions where bits are set (1).
Args:
start: Starting bit position (default 0)
stop: Ending bit position (default -1 for no limit)
Yields:
int: Positions of set bits
"""
def iter_clear(self, start=0, stop=-1):
"""
Iterator over positions where bits are clear (0).
Args:
start: Starting bit position (default 0)
stop: Ending bit position (default -1 for no limit)
Yields:
int: Positions of clear bits
"""Usage Examples
Basic Bit Manipulation
import gmpy2
# Create a test integer
x = gmpy2.mpz(0b11010110) # Binary: 11010110, Decimal: 214
print(f"Original: {x} (binary: {bin(x)})")
# Set bit 0 (rightmost bit)
x_set = gmpy2.bit_set(x, 0)
print(f"Set bit 0: {x_set} (binary: {bin(x_set)})")
# Clear bit 7 (leftmost bit)
x_clear = gmpy2.bit_clear(x, 7)
print(f"Clear bit 7: {x_clear} (binary: {bin(x_clear)})")
# Flip bit 3
x_flip = gmpy2.bit_flip(x, 3)
print(f"Flip bit 3: {x_flip} (binary: {bin(x_flip)})")
# Test specific bits
for i in range(8):
is_set = gmpy2.bit_test(x, i)
print(f"Bit {i}: {'1' if is_set else '0'}")Bit Counting and Analysis
import gmpy2
# Analyze a large integer
large_num = gmpy2.mpz("0xDEADBEEFCAFEBABE")
print(f"Number: {large_num}")
print(f"Hex: {hex(large_num)}")
print(f"Binary length: {gmpy2.bit_length(large_num)} bits")
print(f"Population count: {gmpy2.bit_count(large_num)} set bits")
# Find first set and clear bits
first_set = gmpy2.bit_scan1(large_num, 0)
first_clear = gmpy2.bit_scan0(large_num, 0)
print(f"First set bit at position: {first_set}")
print(f"First clear bit at position: {first_clear}")
# Find next clear bit after position 10
next_clear = gmpy2.bit_scan0(large_num, 10)
print(f"First clear bit after position 10: {next_clear}")Hamming Distance
import gmpy2
# Compare two binary strings
a = gmpy2.mpz("0b11010110")
b = gmpy2.mpz("0b10110101")
print(f"A: {a} (binary: {bin(a)})")
print(f"B: {b} (binary: {bin(b)})")
# Calculate Hamming distance
distance = gmpy2.hamdist(a, b)
print(f"Hamming distance: {distance}")
# Verify by XOR and population count
xor_result = a ^ b
pop_count = gmpy2.popcount(xor_result)
print(f"XOR result: {xor_result} (binary: {bin(xor_result)})")
print(f"Population count of XOR: {pop_count}")
print(f"Verification: {distance == pop_count}")Bit Masks
import gmpy2
# Create various bit masks
mask_4 = gmpy2.bit_mask(4) # 0b1111
mask_8 = gmpy2.bit_mask(8) # 0b11111111
mask_16 = gmpy2.bit_mask(16) # 0b1111111111111111
print(f"4-bit mask: {mask_4} (binary: {bin(mask_4)})")
print(f"8-bit mask: {mask_8} (binary: {bin(mask_8)})")
print(f"16-bit mask: {mask_16} (binary: {bin(mask_16)})")
# Use masks to extract bit fields
value = gmpy2.mpz(0xABCD)
print(f"Original value: {value} (hex: {hex(value)})")
# Extract lower 8 bits
lower_8 = value & mask_8
print(f"Lower 8 bits: {lower_8} (hex: {hex(lower_8)})")
# Extract upper 8 bits
upper_8 = (value >> 8) & mask_8
print(f"Upper 8 bits: {upper_8} (hex: {hex(upper_8)})")Advanced Bit Iteration with xmpz
import gmpy2
# Create mutable integer for efficient bit manipulation
x = gmpy2.xmpz(0b11010110)
print(f"Original: {x} (binary: {bin(x)})")
# Iterate over set bits
print("Set bit positions:")
for pos in x.iter_set():
if pos > 10: # Limit output
break
print(f" Bit {pos} is set")
# Iterate over clear bits in a range
print("Clear bit positions (0-7):")
for pos in x.iter_clear(0, 8):
print(f" Bit {pos} is clear")
# Iterate over all bit positions in a range
print("All bit positions (0-7):")
for pos in x.iter_bits(0, 8):
is_set = gmpy2.bit_test(x, pos)
print(f" Bit {pos}: {'1' if is_set else '0'}")Integer Square Roots
import gmpy2
# Perfect square
perfect = gmpy2.mpz(144)
sqrt_perfect = gmpy2.isqrt(perfect)
sqrt_rem_perfect = gmpy2.isqrt_rem(perfect)
print(f"isqrt({perfect}) = {sqrt_perfect}")
print(f"isqrt_rem({perfect}) = {sqrt_rem_perfect}")
# Non-perfect square
non_perfect = gmpy2.mpz(150)
sqrt_non_perfect = gmpy2.isqrt(non_perfect)
sqrt_rem_non_perfect = gmpy2.isqrt_rem(non_perfect)
print(f"isqrt({non_perfect}) = {sqrt_non_perfect}")
print(f"isqrt_rem({non_perfect}) = {sqrt_rem_non_perfect}")
# Verify: root² + remainder = original
root, remainder = sqrt_rem_non_perfect
verification = root * root + remainder
print(f"Verification: {root}² + {remainder} = {verification}")
# Integer cube root
large_cube = gmpy2.mpz(27000) # 30³ = 27000
cube_root = gmpy2.iroot(large_cube, 3)
print(f"iroot({large_cube}, 3) = {cube_root}")Cryptographic Applications
import gmpy2
def find_hamming_weight_subset(target_weight, bit_length):
"""Find integers with specific Hamming weight."""
results = []
# Check numbers up to 2^bit_length
max_val = 2 ** bit_length
for i in range(min(1000, max_val)): # Limit search for demo
if gmpy2.popcount(i) == target_weight:
results.append(i)
if len(results) >= 5: # Limit results
break
return results
# Find 8-bit numbers with exactly 3 bits set
weight_3_numbers = find_hamming_weight_subset(3, 8)
print("8-bit numbers with Hamming weight 3:")
for num in weight_3_numbers:
print(f" {num} (binary: {bin(num)})")
def bit_reversal(x, width):
"""Reverse the bits in an integer of given width."""
result = gmpy2.mpz(0)
for i in range(width):
if gmpy2.bit_test(x, i):
result = gmpy2.bit_set(result, width - 1 - i)
return result
# Demonstrate bit reversal
original = gmpy2.mpz(0b11010110)
reversed_bits = bit_reversal(original, 8)
print(f"Original: {original} (binary: {bin(original)})")
print(f"Reversed: {reversed_bits} (binary: {bin(reversed_bits)})")Install with Tessl CLI
npx tessl i tessl/pypi-gmpy2