0
# Bit Operations
1
2
gmpy2 provides comprehensive bit manipulation operations for integer types (mpz and xmpz). These operations are highly optimized and work efficiently with arbitrarily large integers.
3
4
## Capabilities
5
6
### Basic Bit Operations
7
8
Fundamental bit manipulation functions for setting, clearing, and testing individual bits.
9
10
```python { .api }
11
def bit_set(x, n):
12
"""
13
Set bit n in integer x.
14
15
Args:
16
x: Integer value (mpz, xmpz, or int)
17
n: Bit position (0-based, 0 is least significant)
18
19
Returns:
20
New integer with bit n set to 1
21
22
Note:
23
For mpz, returns new object. For xmpz methods, modifies in place.
24
"""
25
26
def bit_clear(x, n):
27
"""
28
Clear bit n in integer x.
29
30
Args:
31
x: Integer value
32
n: Bit position (0-based)
33
34
Returns:
35
New integer with bit n set to 0
36
"""
37
38
def bit_flip(x, n):
39
"""
40
Flip (toggle) bit n in integer x.
41
42
Args:
43
x: Integer value
44
n: Bit position (0-based)
45
46
Returns:
47
New integer with bit n flipped
48
"""
49
50
def bit_test(x, n):
51
"""
52
Test if bit n is set in integer x.
53
54
Args:
55
x: Integer value
56
n: Bit position (0-based)
57
58
Returns:
59
bool: True if bit n is 1, False if bit n is 0
60
"""
61
```
62
63
### Bit Counting and Scanning
64
65
Functions for analyzing bit patterns and finding specific bits.
66
67
```python { .api }
68
def bit_count(x):
69
"""
70
Count the number of set bits (population count).
71
72
Args:
73
x: Integer value
74
75
Returns:
76
int: Number of bits set to 1
77
78
Note:
79
Also available as popcount(x)
80
"""
81
82
def popcount(x):
83
"""
84
Population count (alias for bit_count).
85
86
Args:
87
x: Integer value
88
89
Returns:
90
int: Number of bits set to 1
91
"""
92
93
def bit_length(x):
94
"""
95
Number of bits needed to represent the integer.
96
97
Args:
98
x: Integer value
99
100
Returns:
101
int: Number of bits in binary representation (excluding sign)
102
103
Note:
104
For negative numbers, returns length of absolute value
105
"""
106
107
def bit_scan0(x, start=0):
108
"""
109
Find the first clear bit (0) starting from a position.
110
111
Args:
112
x: Integer value
113
start: Starting bit position (default 0)
114
115
Returns:
116
int: Position of first clear bit >= start, or None if none found
117
"""
118
119
def bit_scan1(x, start=0):
120
"""
121
Find the first set bit (1) starting from a position.
122
123
Args:
124
x: Integer value
125
start: Starting bit position (default 0)
126
127
Returns:
128
int: Position of first set bit >= start, or None if none found
129
"""
130
```
131
132
### Bit Mask Operations
133
134
Functions for creating and working with bit masks.
135
136
```python { .api }
137
def bit_mask(n):
138
"""
139
Create a mask with n bits set to 1.
140
141
Args:
142
n: Number of bits to set
143
144
Returns:
145
mpz: Integer with lowest n bits set to 1
146
147
Example:
148
bit_mask(4) returns 15 (binary: 1111)
149
"""
150
151
def xbit_mask(n):
152
"""
153
Create an xmpz mask with n bits set to 1.
154
155
Args:
156
n: Number of bits to set
157
158
Returns:
159
xmpz: Mutable integer with lowest n bits set to 1
160
"""
161
```
162
163
### Hamming Distance
164
165
Function for computing bit difference between integers.
166
167
```python { .api }
168
def hamdist(x, y):
169
"""
170
Compute Hamming distance between two integers.
171
172
Args:
173
x, y: Integer values
174
175
Returns:
176
int: Number of bit positions where x and y differ
177
178
Note:
179
Equivalent to popcount(x ^ y)
180
"""
181
```
182
183
### Integer Root Operations with Remainder
184
185
Functions for integer square roots and higher roots with bit-based implementation.
186
187
```python { .api }
188
def isqrt(x):
189
"""
190
Integer square root.
191
192
Args:
193
x: Non-negative integer
194
195
Returns:
196
mpz: Largest integer n such that n² <= x
197
"""
198
199
def isqrt_rem(x):
200
"""
201
Integer square root with remainder.
202
203
Args:
204
x: Non-negative integer
205
206
Returns:
207
tuple: (root, remainder) where x = root² + remainder
208
"""
209
210
def iroot(x, n):
211
"""
212
Integer nth root.
213
214
Args:
215
x: Integer value
216
n: Root degree (positive integer)
217
218
Returns:
219
tuple: (root, is_exact) where is_exact indicates if root is exact
220
"""
221
222
def iroot_rem(x, n):
223
"""
224
Integer nth root with remainder.
225
226
Args:
227
x: Integer value
228
n: Root degree (positive integer)
229
230
Returns:
231
tuple: (root, remainder) where x = root^n + remainder
232
"""
233
```
234
235
### Advanced Bit Iteration (xmpz only)
236
237
Advanced bit iteration methods available for mutable integers.
238
239
```python { .api }
240
# Note: These are methods of xmpz class, shown for completeness
241
class xmpz:
242
def iter_bits(self, start=0, stop=-1):
243
"""
244
Iterator over all bit positions (both set and clear).
245
246
Args:
247
start: Starting bit position (default 0)
248
stop: Ending bit position (default -1 for no limit)
249
250
Yields:
251
int: Bit positions in order
252
"""
253
254
def iter_set(self, start=0, stop=-1):
255
"""
256
Iterator over positions where bits are set (1).
257
258
Args:
259
start: Starting bit position (default 0)
260
stop: Ending bit position (default -1 for no limit)
261
262
Yields:
263
int: Positions of set bits
264
"""
265
266
def iter_clear(self, start=0, stop=-1):
267
"""
268
Iterator over positions where bits are clear (0).
269
270
Args:
271
start: Starting bit position (default 0)
272
stop: Ending bit position (default -1 for no limit)
273
274
Yields:
275
int: Positions of clear bits
276
"""
277
```
278
279
## Usage Examples
280
281
### Basic Bit Manipulation
282
283
```python
284
import gmpy2
285
286
# Create a test integer
287
x = gmpy2.mpz(0b11010110) # Binary: 11010110, Decimal: 214
288
print(f"Original: {x} (binary: {bin(x)})")
289
290
# Set bit 0 (rightmost bit)
291
x_set = gmpy2.bit_set(x, 0)
292
print(f"Set bit 0: {x_set} (binary: {bin(x_set)})")
293
294
# Clear bit 7 (leftmost bit)
295
x_clear = gmpy2.bit_clear(x, 7)
296
print(f"Clear bit 7: {x_clear} (binary: {bin(x_clear)})")
297
298
# Flip bit 3
299
x_flip = gmpy2.bit_flip(x, 3)
300
print(f"Flip bit 3: {x_flip} (binary: {bin(x_flip)})")
301
302
# Test specific bits
303
for i in range(8):
304
is_set = gmpy2.bit_test(x, i)
305
print(f"Bit {i}: {'1' if is_set else '0'}")
306
```
307
308
### Bit Counting and Analysis
309
310
```python
311
import gmpy2
312
313
# Analyze a large integer
314
large_num = gmpy2.mpz("0xDEADBEEFCAFEBABE")
315
print(f"Number: {large_num}")
316
print(f"Hex: {hex(large_num)}")
317
print(f"Binary length: {gmpy2.bit_length(large_num)} bits")
318
print(f"Population count: {gmpy2.bit_count(large_num)} set bits")
319
320
# Find first set and clear bits
321
first_set = gmpy2.bit_scan1(large_num, 0)
322
first_clear = gmpy2.bit_scan0(large_num, 0)
323
print(f"First set bit at position: {first_set}")
324
print(f"First clear bit at position: {first_clear}")
325
326
# Find next clear bit after position 10
327
next_clear = gmpy2.bit_scan0(large_num, 10)
328
print(f"First clear bit after position 10: {next_clear}")
329
```
330
331
### Hamming Distance
332
333
```python
334
import gmpy2
335
336
# Compare two binary strings
337
a = gmpy2.mpz("0b11010110")
338
b = gmpy2.mpz("0b10110101")
339
340
print(f"A: {a} (binary: {bin(a)})")
341
print(f"B: {b} (binary: {bin(b)})")
342
343
# Calculate Hamming distance
344
distance = gmpy2.hamdist(a, b)
345
print(f"Hamming distance: {distance}")
346
347
# Verify by XOR and population count
348
xor_result = a ^ b
349
pop_count = gmpy2.popcount(xor_result)
350
print(f"XOR result: {xor_result} (binary: {bin(xor_result)})")
351
print(f"Population count of XOR: {pop_count}")
352
print(f"Verification: {distance == pop_count}")
353
```
354
355
### Bit Masks
356
357
```python
358
import gmpy2
359
360
# Create various bit masks
361
mask_4 = gmpy2.bit_mask(4) # 0b1111
362
mask_8 = gmpy2.bit_mask(8) # 0b11111111
363
mask_16 = gmpy2.bit_mask(16) # 0b1111111111111111
364
365
print(f"4-bit mask: {mask_4} (binary: {bin(mask_4)})")
366
print(f"8-bit mask: {mask_8} (binary: {bin(mask_8)})")
367
print(f"16-bit mask: {mask_16} (binary: {bin(mask_16)})")
368
369
# Use masks to extract bit fields
370
value = gmpy2.mpz(0xABCD)
371
print(f"Original value: {value} (hex: {hex(value)})")
372
373
# Extract lower 8 bits
374
lower_8 = value & mask_8
375
print(f"Lower 8 bits: {lower_8} (hex: {hex(lower_8)})")
376
377
# Extract upper 8 bits
378
upper_8 = (value >> 8) & mask_8
379
print(f"Upper 8 bits: {upper_8} (hex: {hex(upper_8)})")
380
```
381
382
### Advanced Bit Iteration with xmpz
383
384
```python
385
import gmpy2
386
387
# Create mutable integer for efficient bit manipulation
388
x = gmpy2.xmpz(0b11010110)
389
print(f"Original: {x} (binary: {bin(x)})")
390
391
# Iterate over set bits
392
print("Set bit positions:")
393
for pos in x.iter_set():
394
if pos > 10: # Limit output
395
break
396
print(f" Bit {pos} is set")
397
398
# Iterate over clear bits in a range
399
print("Clear bit positions (0-7):")
400
for pos in x.iter_clear(0, 8):
401
print(f" Bit {pos} is clear")
402
403
# Iterate over all bit positions in a range
404
print("All bit positions (0-7):")
405
for pos in x.iter_bits(0, 8):
406
is_set = gmpy2.bit_test(x, pos)
407
print(f" Bit {pos}: {'1' if is_set else '0'}")
408
```
409
410
### Integer Square Roots
411
412
```python
413
import gmpy2
414
415
# Perfect square
416
perfect = gmpy2.mpz(144)
417
sqrt_perfect = gmpy2.isqrt(perfect)
418
sqrt_rem_perfect = gmpy2.isqrt_rem(perfect)
419
420
print(f"isqrt({perfect}) = {sqrt_perfect}")
421
print(f"isqrt_rem({perfect}) = {sqrt_rem_perfect}")
422
423
# Non-perfect square
424
non_perfect = gmpy2.mpz(150)
425
sqrt_non_perfect = gmpy2.isqrt(non_perfect)
426
sqrt_rem_non_perfect = gmpy2.isqrt_rem(non_perfect)
427
428
print(f"isqrt({non_perfect}) = {sqrt_non_perfect}")
429
print(f"isqrt_rem({non_perfect}) = {sqrt_rem_non_perfect}")
430
431
# Verify: root² + remainder = original
432
root, remainder = sqrt_rem_non_perfect
433
verification = root * root + remainder
434
print(f"Verification: {root}² + {remainder} = {verification}")
435
436
# Integer cube root
437
large_cube = gmpy2.mpz(27000) # 30³ = 27000
438
cube_root = gmpy2.iroot(large_cube, 3)
439
print(f"iroot({large_cube}, 3) = {cube_root}")
440
```
441
442
### Cryptographic Applications
443
444
```python
445
import gmpy2
446
447
def find_hamming_weight_subset(target_weight, bit_length):
448
"""Find integers with specific Hamming weight."""
449
results = []
450
451
# Check numbers up to 2^bit_length
452
max_val = 2 ** bit_length
453
454
for i in range(min(1000, max_val)): # Limit search for demo
455
if gmpy2.popcount(i) == target_weight:
456
results.append(i)
457
if len(results) >= 5: # Limit results
458
break
459
460
return results
461
462
# Find 8-bit numbers with exactly 3 bits set
463
weight_3_numbers = find_hamming_weight_subset(3, 8)
464
print("8-bit numbers with Hamming weight 3:")
465
for num in weight_3_numbers:
466
print(f" {num} (binary: {bin(num)})")
467
468
def bit_reversal(x, width):
469
"""Reverse the bits in an integer of given width."""
470
result = gmpy2.mpz(0)
471
for i in range(width):
472
if gmpy2.bit_test(x, i):
473
result = gmpy2.bit_set(result, width - 1 - i)
474
return result
475
476
# Demonstrate bit reversal
477
original = gmpy2.mpz(0b11010110)
478
reversed_bits = bit_reversal(original, 8)
479
print(f"Original: {original} (binary: {bin(original)})")
480
print(f"Reversed: {reversed_bits} (binary: {bin(reversed_bits)})")
481
```