DSPython  00.03.03 — 25 juin 2012
 Tout Classes Espaces de nommage Fichiers Fonctions Variables Pages
bit32.py
Aller à la documentation de ce fichier.
1 #!/usr/bin/env python
2 # -*- coding: latin-1 -*-
3 ##\package DSPython.bit32 Bits de naturels sur 32 bits
4 
5 ##\file
6 # Bits de naturels sur 32 bits
7 
8 # (c) Olivier Pirson --- DragonSoft
9 # http://www.opimedia.be/DS/
10 # Débuté le 30 juillet 2006
11 ####################################
12 from __future__ import print_function
13 
14 ## Date du dernier changement pour ce module
15 VERSION = 'bit32 --- 2010 March 16'
16 
17 import DSPython
18 
19 
20 
21 # ############
22 # Constantes #
23 ##############
24 ## Représentation binaire des naturels tenant sur 8 bits
25 BIN_8_TUPLE = ('0', '1', '10', '11',
26  '100', '101', '110', '111',
27  '1000', '1001', '1010', '1011',
28  '1100', '1101', '1110', '1111',
29  '10000', '10001', '10010', '10011',
30  '10100', '10101', '10110', '10111',
31  '11000', '11001', '11010', '11011',
32  '11100', '11101', '11110', '11111',
33  '100000', '100001', '100010', '100011',
34  '100100', '100101', '100110', '100111',
35  '101000', '101001', '101010', '101011',
36  '101100', '101101', '101110', '101111',
37  '110000', '110001', '110010', '110011',
38  '110100', '110101', '110110', '110111',
39  '111000', '111001', '111010', '111011',
40  '111100', '111101', '111110', '111111',
41  '1000000', '1000001', '1000010', '1000011',
42  '1000100', '1000101', '1000110', '1000111',
43  '1001000', '1001001', '1001010', '1001011',
44  '1001100', '1001101', '1001110', '1001111',
45  '1010000', '1010001', '1010010', '1010011',
46  '1010100', '1010101', '1010110', '1010111',
47  '1011000', '1011001', '1011010', '1011011',
48  '1011100', '1011101', '1011110', '1011111',
49  '1100000', '1100001', '1100010', '1100011',
50  '1100100', '1100101', '1100110', '1100111',
51  '1101000', '1101001', '1101010', '1101011',
52  '1101100', '1101101', '1101110', '1101111',
53  '1110000', '1110001', '1110010', '1110011',
54  '1110100', '1110101', '1110110', '1110111',
55  '1111000', '1111001', '1111010', '1111011',
56  '1111100', '1111101', '1111110', '1111111',
57  '10000000', '10000001', '10000010', '10000011',
58  '10000100', '10000101', '10000110', '10000111',
59  '10001000', '10001001', '10001010', '10001011',
60  '10001100', '10001101', '10001110', '10001111',
61  '10010000', '10010001', '10010010', '10010011',
62  '10010100', '10010101', '10010110', '10010111',
63  '10011000', '10011001', '10011010', '10011011',
64  '10011100', '10011101', '10011110', '10011111',
65  '10100000', '10100001', '10100010', '10100011',
66  '10100100', '10100101', '10100110', '10100111',
67  '10101000', '10101001', '10101010', '10101011',
68  '10101100', '10101101', '10101110', '10101111',
69  '10110000', '10110001', '10110010', '10110011',
70  '10110100', '10110101', '10110110', '10110111',
71  '10111000', '10111001', '10111010', '10111011',
72  '10111100', '10111101', '10111110', '10111111',
73  '11000000', '11000001', '11000010', '11000011',
74  '11000100', '11000101', '11000110', '11000111',
75  '11001000', '11001001', '11001010', '11001011',
76  '11001100', '11001101', '11001110', '11001111',
77  '11010000', '11010001', '11010010', '11010011',
78  '11010100', '11010101', '11010110', '11010111',
79  '11011000', '11011001', '11011010', '11011011',
80  '11011100', '11011101', '11011110', '11011111',
81  '11100000', '11100001', '11100010', '11100011',
82  '11100100', '11100101', '11100110', '11100111',
83  '11101000', '11101001', '11101010', '11101011',
84  '11101100', '11101101', '11101110', '11101111',
85  '11110000', '11110001', '11110010', '11110011',
86  '11110100', '11110101', '11110110', '11110111',
87  '11111000', '11111001', '11111010', '11111011',
88  '11111100', '11111101', '11111110', '11111111')
89 
90 
91 ## Nombre de Mersenne M<sub>8</sub> == 2<sup>8</sup>
92 MERSENNE8 = 255
93 ## Nombre de Mersenne M<sub>16</sub> == 2<sup>16</sup>
94 MERSENNE16 = 65535
95 ## Nombre de Mersenne M<sub>24</sub> == 2<sup>24</sup>
96 MERSENNE24 = 16777215
97 ## Nombre de Mersenne M<sub>32</sub> == 2<sup>32</sup>
98 MERSENNE32 = 4294967295
99 
100 
101 ## Nombres de Mersenne M<sub>n</sub> tenant sur 32 bits
102 MERSENNE_TUPLE = (0, 1, 3, 7,
103  15, 31, 63, 127,
104  MERSENNE8, 511, 1023, 2047,
105  4095, 8191, 16383, 32767,
106  MERSENNE16, 131071, 262143, 524287,
107  1048575, 2097151, 4194303, 8388607,
108  MERSENNE24, 33554431, 67108863, 134217727,
109  268435455, 536870911, 1073741823, 2147483647,
110  MERSENNE32)
111 
112 
113 ## Nombre de bits à 1 pour les naturels tenant sur 8 bits
114 NBBITS1_8_TUPLE = (0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
115  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
116  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
117  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
118  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
119  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
120  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
121  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
122  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
123  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
124  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
125  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
126  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
127  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
128  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
129  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8)
130 
131 
132 ## Nombre de bits pour les naturels tenant sur 8 bits
133 NBBITS_8_TUPLE = (0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
134  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
135  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
136  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
137  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
138  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
139  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
140  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
141  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
142  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
143  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
144  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
145  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
146  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
147  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
148  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8)
149 
150 
151 ## 2<sup>k</sup>, puissances de 2 tenant sur 32 bits
152 POW2_TUPLE = (1, 2, 4, 8,
153  16, 32, 64, 128,
154  256, 512, 1024, 2048,
155  4096, 8192, 16384, 32768,
156  65536, 131072, 262144, 524288,
157  1048576, 2097152, 4194304, 8388608,
158  16777216, 33554432, 67108864, 134217728,
159  268435456, 536870912, 1073741824, 2147483648)
160 
161 
162 ## Indice du dernier bit à 0 pour les naturels tenant sur 8 bits
163 RSCAN0_8_TUPLE = (None, None, 0, None, 1, 1, 0, None, 2, 2, 2, 2, 1, 1, 0, None,
164  3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 0, None,
165  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
166  3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 0, None,
167  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
168  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
169  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
170  3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 0, None,
171  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
172  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
173  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
174  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
175  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
176  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
177  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
178  3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 0, None)
179 
180 
181 ## Indice du premier bit à 0 pour les naturels impairs tenant sur 8 bits
182 SCAN0_ODD8_TUPLE = (1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
183  1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6,
184  1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
185  1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7,
186  1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
187  1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6,
188  1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
189  1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8)
190 
191 
192 ## Indice du premier bit à 1 pour les naturels pairs tenant sur 8 bits, ou None
193 SCAN1_EVEN8_TUPLE = (None, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
194  5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
195  6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
196  5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
197  7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
198  5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
199  6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1,
200  5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1)
201 
202 
203 
204 # ###########
205 # Fonctions #
206 #############
207 ## n en binaire dans un string
208 def bin(n):
209  """Renvoie un string représentant n en binaire
210  (Si n == 0 alors renvoie '0')
211 
212  Pre: n naturel < 2**32
213 
214  Result: string de 1 <= longueur <= 32
215 
216  O(n) = 1"""
217  assert DSPython.nat32_is(n), n
218 
219  if n <= MERSENNE8:
220  return BIN_8_TUPLE[n]
221  else:
222  l = [BIN_8_TUPLE[n & MERSENNE8]]
223  while n > MERSENNE8:
224  n >>= 8
225  if len(l[0]) < 8: # si faut complèter l'élément précédant avec des '0'
226  l.insert(0, '0' * (8 - len(l[0])))
227  l.insert(0, BIN_8_TUPLE[n & MERSENNE8])
228  return ''.join(l)
229 
230 
231 ## Le bit d'indice i de n vaut 1 ?
232 def bit(n, i):
233  """Renvoie True si le bit d'indice i de n vaut 1,
234  False sinon
235 
236  Pre: n naturel < 2**32
237  i naturel < 32
238 
239  Result: bool
240 
241  O(n) = 1"""
242  assert DSPython.nat32_is(n), n
243  assert DSPython.natural_is(i), i
244  assert i < 32, i
245 
246  return bool(n & (1 << i))
247 
248 
249 ## n avec son bit d'indice i à b
250 def bitset(n, i, b):
251  """Si b alors renvoie n avec son bit d'indice i à 1,
252  sinon renvoie n avec son bit d'indice i à 0
253 
254  Pre: n naturel < 2**32
255  i naturel < 32
256 
257  Result: naturel < 2**32
258 
259  O(n) = 1"""
260  assert DSPython.nat32_is(n), n
261  assert DSPython.natural_is(i), i
262  assert i < 32, i
263 
264  return (n | (1 << i) if b
265  else n & ~(1 << i))
266 
267 
268 ## n avec son bit d'indice i à 0
269 def bitset0(n, i):
270  """Renvoie n avec son bit d'indice i à 0
271 
272  Pre: n naturel < 2**32
273  i naturel < 32
274 
275  Result: naturel < 2**32
276 
277  O(n) = 1"""
278  assert DSPython.nat32_is(n), n
279  assert DSPython.natural_is(i), i
280  assert i < 32, i
281 
282  return n & ~(1 << i)
283 
284 
285 ## n avec son bit d'indice i à 1
286 def bitset1(n, i):
287  """Renvoie n avec son bit d'indice i à 1
288 
289  Pre: n naturel < 2**32
290  i naturel < 32
291 
292  Result: naturel < 2**32
293 
294  O(n) = 1"""
295  assert DSPython.nat32_is(n), n
296  assert DSPython.natural_is(i), i
297  assert i < 32, i
298 
299  return n | (1 << i)
300 
301 
302 ## lg(n) == log<sub>2</sub>(n) == nbbits(n) - 1 == l'indice du dernier bit à 1 de n
303 ## &nbsp; &nbsp; (n != 0)
304 def lg(n):
305  """Renvoie lg(n) == log_2(n) == nbbits(n) - 1
306  == l'indice du dernier bit à 1 de n
307 
308  Pre: n: 1 <= naturel < 2**32
309 
310  Result: naturel < 32
311 
312  O(n) = 1"""
313  assert DSPython.nat32_is(n), n
314 
315  return nbbits(n) - 1
316 
317 
318 ## M<sub>k</sub> == 2<sup>k</sup> - 1
319 def mersenne(k):
320  """Renvoie le nième nombre de Mersenne M_k == 2**k - 1
321 
322  Pre: k: naturel <= 32
323 
324  Result: naturel < 2**32
325 
326  O(k) = 1"""
327  assert DSPython.natural_is(k), k
328  assert k <= 32, k
329 
330  return MERSENNE_TUPLE[k]
331 
332 
333 ## n est un nombre de Mersenne ?
334 def mersenne_is(n):
335  """Renvoie True si n est un nombre de Mersenne,
336  False sinon
337 
338  Pre: n: naturel < 2**32
339 
340  Result: bool
341 
342  O(n) = 1"""
343  assert DSPython.nat32_is(n), n
344 
345  return MERSENNE_TUPLE[scan0(n)] == n
346 
347 
348 ## Indice du nombre de Mersenne correspondant à n, ou None
349 def mersenne_to_index(n):
350  """Si n == M_k alors renvoie k
351  sinon renvoie None
352 
353  Pre: n: naturel < 2**32
354 
355  Result: naturel <= 32 ou None
356 
357  O(n) = 1"""
358  assert DSPython.nat32_is(n), n
359 
360  i = scan0(n)
361  return (i if MERSENNE_TUPLE[i] == n
362  else None)
363 
364 
365 ## Nombre de bits à 0 de n
366 def nbbits0(n):
367  """Renvoie le nombre de bits à 0 de n
368  (sans tenir compte des 0 après le dernier 1)
369  (Si n == 0 alors renvoie 0)
370 
371  Pre: n: naturel < 2**32
372 
373  Result: naturel <= 31
374 
375  O(n) = 1"""
376  assert DSPython.nat32_is(n), n
377 
378  return nbbits(n) - nbbits1(n)
379 
380 
381 ## Nombre de bits à 1 de n
382 def nbbits1(n):
383  """Renvoie le nombre de bits à 1 de n
384  (Si n == 0 alors renvoie 0)
385 
386  Pre: n: naturel < 2**32
387 
388  Result: naturel <= 32
389 
390  O(n) = 1"""
391  assert DSPython.nat32_is(n), n
392 
393  return (NBBITS1_8_TUPLE[n >> 24] + NBBITS1_8_TUPLE[(n >> 16) & MERSENNE8]
394  + NBBITS1_8_TUPLE[(n >> 8) & MERSENNE8] + NBBITS1_8_TUPLE[n & MERSENNE8])
395 
396 
397 ## Nombre de bits de n
398 def nbbits(n):
399  """Renvoie le nombre de bits de n
400  == nbbits0(n) + nbbits1(n)
401  (sans tenir compte des 0 après le dernier 1)
402  (Si n == 0 alors renvoie 0)
403 
404  Pre: n: naturel < 2**32
405 
406  Result: naturel <= 32
407 
408  O(n) = 1"""
409  assert DSPython.nat32_is(n), n
410 
411  h = n >> 16
412  if h != 0:
413  if (h>>8) != 0: # 2**24 <= n < 2**32
414  return NBBITS_8_TUPLE[h >> 8] + 24
415  else: # 2**16 <= n < 2**24
416  return NBBITS_8_TUPLE[h & MERSENNE8] + 16
417  else:
418  if (n>>8) != 0: # 2**8 <= n < 2*16
419  return NBBITS_8_TUPLE[n>>8 & MERSENNE8] + 8
420  else: # 0 <= n < 2**8
421  return NBBITS_8_TUPLE[n & MERSENNE8]
422 
423 
424 ## 2<sup>k</sup>
425 def pow2(k):
426  """Renvoie la kième puissance de 2 : 2**k
427 
428  Pre: k naturel <= 31
429 
430  Result: 1 <= naturel <= 2**31
431 
432  O(k) = 1"""
433  assert DSPython.natural_is(k), k
434  assert k <= 31, k
435 
436  return POW2_TUPLE[k]
437 
438 
439 ## n est une puissance de 2 ?
440 def pow2_is(n):
441  """Renvoie True si n est une puissance de 2,
442  False sinon
443 
444  Pre: n: naturel < 2**32
445 
446  Result: bool
447 
448  O(n) = 1"""
449  assert DSPython.nat32_is(n), n
450 
451  return (n != 0) and (POW2_TUPLE[rscan1(n)] == n)
452 
453 
454 ## Exposant de la puissance de Mersenne correspondant à n, ou None
455 def pow2_to_index(n):
456  """Si n == 2^k alors renvoie k
457  sinon renvoie None
458 
459  Pre: n: naturel < 2**32
460 
461  Result: naturel <= 32 ou None
462 
463  O(n) = 1"""
464  assert DSPython.nat32_is(n), n
465 
466  i = rscan1(n)
467  return (i if (n != 0) and (POW2_TUPLE[i] == n)
468  else None)
469 
470 
471 ## Indice du dernier bit à 0 de n, ou None
472 def rscan0(n):
473  """Renvoie l'indice du dernier bit à 0 de n
474  ou None si pas de bit à 0 contenu dans n
475 
476  Pre: n: naturel < 2**32
477 
478  Result: naturel <= 32
479 
480  O(n) = 1"""
481  assert DSPython.nat32_is(n), n
482 
483  h = n >> 16
484  if (h&MERSENNE16 != 0) and (h != MERSENNE16):
485  if (h>>8 != 0) and (h>>8 != MERSENNE8):
486  return RSCAN0_8_TUPLE[h >> 8] + 24
487  else:
488  return RSCAN0_8_TUPLE[h & MERSENNE8] + 16
489  else:
490  n &= MERSENNE16
491  if (n>>8 != 0) and (h>>8 != MERSENNE8):
492  return RSCAN0_8_TUPLE[n >> 8] + 8
493  else:
494  return RSCAN0_8_TUPLE[n & MERSENNE8]
495 
496 
497 ## Indice du dernier bit à 1 de, n == nbbits(n) - 1 ou None
498 def rscan1(n):
499  """Renvoie l'indice du dernier bit à 1 de n
500  ou None si n == 0
501 
502  Pre: n: naturel < 2**32
503 
504  Result: naturel <= 31 ou None
505 
506  O(n) = 1"""
507  assert DSPython.nat32_is(n), n
508 
509  return (nbbits(n) - 1 if n > 0
510  else None)
511 
512 
513 ## Indice du premier bit à 0 de n
514 def scan0(n):
515  """Renvoie l'indice du premier bit à 0 de n
516  (si n == 0 alors renvoie 0)
517  (si n == 2**32 - 1 alors renvoie 32)
518 
519  Pre: n: naturel < 2**32
520 
521  Result: naturel <= 32
522 
523  O(n) = 1"""
524  assert DSPython.nat32_is(n), n
525 
526  if n < MERSENNE32: # n contient au moins un 0
527  if (n & MERSENNE16) != MERSENNE16: # n contient au moins un 0 dans les 16 premiers bits
528  if (n & MERSENNE8) != MERSENNE8: # n contient au moins un 0 dans les 8 premiers bits
529  k = 0
530  else:
531  k = 8
532  n >>= 8
533  else: # n contient au moins un 0 dans les 16 derniers bits
534  if (n & (MERSENNE8 << 16)) != (MERSENNE8 << 16):
535  k = 16
536  n >>= 16
537  else: # n contient au moins un 0 dans les 8 derniers bits
538  k = 24
539  n >>= 24
540  return (k if n&1 == 0
541  else k + SCAN0_ODD8_TUPLE[(n & MERSENNE8) >> 1])
542  else: # n == 11111111111111111111111111111111b
543  return 32
544 
545 
546 ## Indice du premier bit à 1 de n, ou None
547 def scan1(n):
548  """Renvoie l'indice du premier bit à 1 de n
549  ou None si n == 0
550 
551  Pre: n: naturel < 2**32
552 
553  Result: naturel < 32 ou None
554 
555  O(n) = 1"""
556  assert DSPython.nat32_is(n), n
557 
558  if n > 0: # n contient au moins un 1
559  if (n & MERSENNE16) != 0: # n contient au moins un 1 dans les 16 premiers bits
560  if (n & MERSENNE8) != 0: # n contient au moins un 1 dans les 8 premiers bits
561  k = 0
562  else:
563  k = 8
564  n >>= 8
565  else: # n contient au moins un 1 dans les 16 derniers bits
566  if (n & (MERSENNE8 << 16)) != 0:
567  k = 16
568  n >>= 16
569  else: # n contient au moins un 1 dans les 8 derniers bits
570  k = 24
571  n >>= 24
572  return (k if n&1 != 0
573  else k + SCAN1_EVEN8_TUPLE[(n & MERSENNE8) >> 1])
574  else: # n == 0
575  return None
576 
577 
578 
579 # ######\cond MAINTEST
580 # Main #
581 ########
582 if __name__ == '__main__':
583  def main_test():
584  """Test du module"""
585  import sys
586 
587  import DSPython.debug as debug
588 
589  try:
590  if not 'profile' in dir():
591  import psyco
592  psyco.full()
593  except ImportError:
594  pass
595 
596  debug.test_begin(VERSION, __debug__)
597 
598  assert len(BIN_8_TUPLE) == 256, len(BIN_8_TUPLE)
599  assert len(MERSENNE_TUPLE) == 33, len(MERSENNE_TUPLE)
600  assert len(NBBITS1_8_TUPLE) == 256, len(NBBITS1_8_TUPLE)
601  assert len(NBBITS_8_TUPLE) == 256, len(NBBITS_8_TUPLE)
602  assert len(POW2_TUPLE) == 32, len(POW2_TUPLE)
603  assert len(RSCAN0_8_TUPLE) == 256, len(RSCAN0_8_TUPLE)
604  assert len(SCAN0_ODD8_TUPLE) == 128, len(SCAN0_ODD8_TUPLE)
605  assert len(SCAN1_EVEN8_TUPLE) == 128, len(SCAN1_EVEN8_TUPLE)
606 
607 
608  print('bin()...', end=''); sys.stdout.flush()
609  assert bin(0) == '0', bin(0)
610  assert bin(1) == '1', bin(1)
611  for i in range(1, 31):
612  assert bin(2**i - 1) == '1'*i, (i, bin(2**i - 1)) # 1...11
613  assert bin(2**i) == '1' + '0'*i, (i, bin(2**i)) # 10...00
614  assert bin(2**i + 1) == '1' + '0'*(i - 1) + '1', (i, bin(2**i + 1)) # 10...01
615  assert bin(2**32 - 1) == '1'*32, bin(2**32)
616  if debug.assertspeed >= debug.ASSERT_NORMAL:
617  for n in range(1, 16384):
618  assert int(bin(n), 2) == n, (n, bin(n))
619  assert len(bin(n)) == nbbits(n), (n, bin(n), nbbits(n))
620  for n in range(1, 2**32, 10000000):
621  assert int(bin(n), 2) == n, (n, bin(n))
622  assert len(bin(n)) == nbbits(n), (n, bin(n), nbbits(n))
623  for n in range(2**32 - 16384, 2**32):
624  assert int(bin(n), 2) == n, (n, bin(n))
625  assert len(bin(n)) == nbbits(n), (n, bin(n), nbbits(n))
626  else:
627  print(debug.assertspeed_str(), end='')
628  print('ok'); sys.stdout.flush()
629 
630 
631  print('bit()...', end=''); sys.stdout.flush()
632  for i in range(32):
633  assert bit(2**i, i) == True, (i, 2**i, bit(2**i, i))
634  for j in range(32):
635  assert bit(0, i) == False, (i, bit(0, i))
636  assert bit(MERSENNE32, i) == True, (i, bit(MERSENNE32, i))
637  if i != j:
638  assert bit(2**i, j) == False, (i, j, 2**i, bit(2**i, j))
639  print('ok'); sys.stdout.flush()
640 
641 
642  print('bitset()...', end=''); sys.stdout.flush()
643  for n in range(2048):
644  for i in range(32):
645  if bit(n, i):
646  assert bitset(n, i, False) == n - (1<<i), (n, n - (1<<i), bitset(n, i, False))
647  assert bitset(n, i, True) == n, (n, bitset(n, i, True))
648  else:
649  assert bitset(n, i, False) == n, (n, bitset(n, i, False))
650  assert bitset(n, i, True) == n + (1<<i), (n, n + (1<<i), bitset(n, i, True))
651  if debug.assertspeed >= debug.ASSERT_NORMAL:
652  for n in range(1, 2**32, 10000000):
653  for i in range(32):
654  if bit(n, i):
655  assert bitset(n, i, False) == n - (1<<i), (n, n - (1<<i),
656  bitset(n, i, False))
657  assert bitset(n, i, True) == n, (n, bitset(n, i, True))
658  else:
659  assert bitset(n, i, False) == n, (n, bitset(n, i, False))
660  assert bitset(n, i, True) == n + (1<<i), (n, n + (1<<i), bitset(n, i, True))
661  for n in range(2**32 - 2048, 2**32):
662  for i in range(32):
663  if bit(n, i):
664  assert bitset(n, i, False) == n - (1<<i), (n, n - (1<<i),
665  bitset(n, i, False))
666  assert bitset(n, i, True) == n, (n, bitset(n, i, True))
667  else:
668  assert bitset(n, i, False) == n, (n, bitset(n, i, False))
669  assert bitset(n, i, True) == n + (1<<i), (n, n + (1<<i), bitset(n, i, True))
670  else:
671  print(debug.assertspeed_str(), end='')
672  print('ok'); sys.stdout.flush()
673 
674 
675  print('bitset0()...', end=''); sys.stdout.flush()
676  for n in range(2048):
677  for i in range(32):
678  if bit(n, i):
679  assert bitset0(n, i) == n - (1<<i), (n, n - (1<<i), bitset0(n, i))
680  else:
681  assert bitset0(n, i) == n, (n, bitset0(n, i))
682  assert bitset0(n, i) == bitset(n, i, False), (n, bitset(n, i, False), bitset0(n, i))
683  if debug.assertspeed >= debug.ASSERT_NORMAL:
684  for n in range(1, 2**32, 10000000):
685  for i in range(32):
686  if bit(n, i):
687  assert bitset0(n, i) == n - (1<<i), (n, n - (1<<i), bitset0(n, i))
688  else:
689  assert bitset0(n, i) == n, (n, bitset0(n, i))
690  assert bitset0(n, i) == bitset(n, i, False), (n, bitset(n, i, False), bitset0(n, i))
691  for n in range(2**32 - 2048, 2**32):
692  for i in range(32):
693  if bit(n, i):
694  assert bitset0(n, i) == n - (1<<i), (n, n - (1<<i), bitset0(n, i))
695  else:
696  assert bitset0(n, i) == n, (n, bitset0(n, i))
697  assert bitset0(n, i) == bitset(n, i, False), (n, bitset(n, i, False), bitset0(n, i))
698  else:
699  print(debug.assertspeed_str(), end='')
700  print('ok'); sys.stdout.flush()
701 
702 
703  print('bitset1()...', end=''); sys.stdout.flush()
704  for n in range(2048):
705  for i in range(32):
706  if bit(n, i):
707  assert bitset1(n, i) == n, (n, bitset1(n, i))
708  else:
709  assert bitset1(n, i) == n + (1<<i), (n, n + (1<<i), bitset1(n, i))
710  assert bitset1(n, i) == bitset(n, i, True), (n, bitset(n, i, True), bitset1(n, i))
711  if debug.assertspeed >= debug.ASSERT_NORMAL:
712  for n in range(1, 2**32, 10000000):
713  for i in range(32):
714  if bit(n, i):
715  assert bitset1(n, i) == n, (n, bitset1(n, i))
716  else:
717  assert bitset1(n, i) == n + (1<<i), (n, n + (1<<i), bitset1(n, i))
718  assert bitset1(n, i) == bitset(n, i, True), (n, bitset(n, i, True), bitset1(n, i))
719  for n in range(2**32 - 2048, 2**32):
720  for i in range(32):
721  if bit(n, i):
722  assert bitset1(n, i) == n, (n, bitset1(n, i))
723  else:
724  assert bitset1(n, i) == n + (1<<i), (n, n + (1<<i), bitset1(n, i))
725  assert bitset1(n, i) == bitset(n, i, True), (n, bitset(n, i, True), bitset1(n, i))
726  else:
727  print(debug.assertspeed_str(), end='')
728  print('ok'); sys.stdout.flush()
729 
730 
731  print('lg()...', end=''); sys.stdout.flush()
732  for n in range(1, 4096):
733  assert lg(n) == len(bin(n)) - 1, (n, lg(n), len(bin(n)))
734  if debug.assertspeed >= debug.ASSERT_NORMAL:
735  for n in range(1, 2**32, 10000000):
736  assert lg(n) == len(bin(n)) - 1, (n, lg(n), len(bin(n)))
737  for n in range(2**32 - 4096, 2**32):
738  assert lg(n) == len(bin(n)) - 1, (n, lg(n), len(bin(n)))
739  else:
740  print(debug.assertspeed_str(), end='')
741  print('ok'); sys.stdout.flush()
742 
743 
744  print('mersenne()...', end=''); sys.stdout.flush()
745  for k in range(33):
746  assert mersenne(k) + 1 == 2**k, (k, mersenne(k))
747  print('ok'); sys.stdout.flush()
748 
749 
750  print('mersenne_is()...', end=''); sys.stdout.flush()
751  assert mersenne_is(0)
752  assert mersenne_is(1)
753  assert not mersenne_is(2)
754  assert mersenne_is(3)
755  for k in range(2, 32):
756  assert not mersenne_is(mersenne(k) - 1), k
757  assert mersenne_is(mersenne(k)), k
758  assert not mersenne_is(mersenne(k) + 1), k
759  print('ok'); sys.stdout.flush()
760 
761 
762  print('mersenne_to_index()...', end=''); sys.stdout.flush()
763  assert mersenne_to_index(0) == 0, mersenne_to_index(0)
764  assert mersenne_to_index(1) == 1, mersenne_to_index(1)
765  assert mersenne_to_index(2) == None, mersenne_to_index(2)
766  assert mersenne_to_index(3) == 2, mersenne_to_index(3)
767  for k in range(2, 32):
768  assert mersenne_to_index(mersenne(k) - 1) == None, \
769  (k, mersenne_to_index(mersenne(k) - 1))
770  assert mersenne_to_index(mersenne(k)) == k, \
771  (k, mersenne_to_index(mersenne(k) ))
772  assert mersenne_to_index(mersenne(k) + 1) == None, \
773  (k, mersenne_to_index(mersenne(k) + 1))
774  print('ok'); sys.stdout.flush()
775 
776 
777  print('nbbits0()...', end=''); sys.stdout.flush()
778  assert nbbits0(0) == 0
779  for n in range(1, 4096):
780  nb = 0
781  for i in range(rscan1(n)):
782  if not bit(n, i):
783  nb += 1
784  assert nbbits0(n) == nb, (n, nb, nbbits0(n))
785  if debug.assertspeed >= debug.ASSERT_NORMAL:
786  for n in range(1, 2**32, 10000000):
787  nb = 0
788  for i in range(rscan1(n)):
789  if not bit(n, i):
790  nb += 1
791  assert nbbits0(n) == nb, (n, nb, nbbits0(n))
792  for n in range(2**32 - 4096, 2**32):
793  nb = 0
794  for i in range(rscan1(n)):
795  if not bit(n, i):
796  nb += 1
797  assert nbbits0(n) == nb, (n, nb, nbbits0(n))
798  else:
799  print(debug.assertspeed_str(), end='')
800  print('ok'); sys.stdout.flush()
801 
802 
803  print('nbbits1()...', end=''); sys.stdout.flush()
804  assert nbbits1(0) == 0
805  for n in range(4096):
806  nb = 0
807  for i in range(32):
808  if bit(n, i):
809  nb += 1
810  assert nbbits1(n) == nb, (n, nb, nbbits1(n))
811  if debug.assertspeed >= debug.ASSERT_NORMAL:
812  for n in range(1, 2**32, 10000000):
813  nb = 0
814  for i in range(32):
815  if bit(n, i):
816  nb += 1
817  assert nbbits1(n) == nb, (n, nb, nbbits1(n))
818  for n in range(2**32 - 4096, 2**32):
819  nb = 0
820  for i in range(32):
821  if bit(n, i):
822  nb += 1
823  assert nbbits1(n) == nb, (n, nb, nbbits1(n))
824  else:
825  print(debug.assertspeed_str(), end='')
826  print('ok'); sys.stdout.flush()
827 
828 
829  print('nbbits()...', end=''); sys.stdout.flush()
830  assert nbbits(0) == 0
831  assert nbbits(1) == 1
832  assert nbbits(2) == 2
833  assert nbbits(3) == 2
834  assert nbbits(4) == 3
835  for n in range(1, 4096):
836  l = nbbits(n)
837  assert (1<<(l - 1)) <= n, (n, l)
838  assert n < (1<<l), (n, l)
839  assert nbbits(n) == len(bin(n)), (n, nbbits(n), bin(n))
840  if debug.assertspeed >= debug.ASSERT_NORMAL:
841  for n in range(1, 2**32, 10000000):
842  l = nbbits(n)
843  assert (1<<(l - 1)) <= n, (n, l)
844  assert n < (1<<l), (n, l)
845  assert nbbits(n) == len(bin(n)), (n, nbbits(n), bin(n))
846  for n in range(2**32-4096, 2**32):
847  l = nbbits(n)
848  assert (1<<(l - 1)) <= n, (n, l)
849  assert n < (1<<l), (n, l)
850  assert nbbits(n) == len(bin(n)), (n, nbbits(n), bin(n))
851  else:
852  print(debug.assertspeed_str(), end='')
853  print('ok'); sys.stdout.flush()
854 
855 
856  print('pow2()...', end=''); sys.stdout.flush()
857  for k in range(32):
858  assert pow2(k) == 2**k, (k, pow2(k))
859  print('ok'); sys.stdout.flush()
860 
861 
862  print('pow2_is()...', end=''); sys.stdout.flush()
863  assert not pow2_is(0)
864  assert pow2_is(1)
865  assert pow2_is(2)
866  assert not pow2_is(3)
867  assert pow2_is(4)
868  assert not pow2_is(5)
869  for k in range(2, 32):
870  assert not pow2_is(pow2(k) - 1), k
871  assert pow2_is(pow2(k)), k
872  assert not pow2_is(pow2(k) + 1), k
873  print('ok'); sys.stdout.flush()
874 
875 
876  print('pow2_to_index()...', end=''); sys.stdout.flush()
877  assert pow2_to_index(0) == None, pow2_to_index(0)
878  assert pow2_to_index(1) == 0, pow2_to_index(1)
879  assert pow2_to_index(2) == 1, pow2_to_index(2)
880  assert pow2_to_index(3) == None, pow2_to_index(3)
881  assert pow2_to_index(4) == 2, pow2_to_index(4)
882  assert pow2_to_index(5) == None, pow2_to_index(5)
883  for k in range(2, 32):
884  assert pow2_to_index(pow2(k) - 1) == None, \
885  (k, pow2_to_index(pow2(k) - 1))
886  assert pow2_to_index(pow2(k)) == k, \
887  (k, pow2_to_index(pow2(k) ))
888  assert pow2_to_index(pow2(k) + 1) == None, \
889  (k, pow2_to_index(pow2(k) + 1))
890  print('ok'); sys.stdout.flush()
891 
892 
893  print('rscan0()...', end=''); sys.stdout.flush()
894  assert rscan0(0) == None
895  assert rscan0(1) == None
896  assert rscan0(2) == 0
897  assert rscan0(3) == None
898  assert rscan0(4) == 1
899  assert rscan0(5) == 1
900  assert rscan0(MERSENNE32) == None
901  for n in range(4096):
902  k = None
903  for i in range(nbbits(n) - 1, -1, 1):
904  if not bit(n, i):
905  k = i
906  break
907  assert rscan0(n) == k, (n, rscan0(n), k)
908  if debug.assertspeed >= debug.ASSERT_NORMAL:
909  for n in range(1, 2**32, 10000000):
910  k = None
911  for i in range(nbbits(n) - 1, -1, 1):
912  if not bit(n, i):
913  k = i
914  break
915  assert rscan0(n) == k, (n, rscan0(n), k)
916  for n in range(2**32 - 4096, 2**32):
917  k = None
918  for i in range(nbbits(n) - 1, -1, 1):
919  if not bit(n, i):
920  k = i
921  break
922  assert rscan0(n) == k, (n, rscan0(n), k)
923  else:
924  print(debug.assertspeed_str(), end='')
925  print('ok'); sys.stdout.flush()
926 
927 
928  print('rscan1()...', end=''); sys.stdout.flush()
929  assert rscan1(0) == None
930  assert rscan1(1) == 0
931  assert rscan1(2) == 1
932  assert rscan1(3) == 1
933  assert rscan1(4) == 2
934  assert rscan1(5) == 2
935  assert rscan1(MERSENNE32) == 31
936  for n in range(1, 4096):
937  assert rscan1(n) == len(bin(n)) - 1, (n, rscan1(n), len(bin(n)))
938  if debug.assertspeed >= debug.ASSERT_NORMAL:
939  for n in range(1, 2**32, 10000000):
940  assert rscan1(n) == len(bin(n)) - 1, (n, rscan1(n), len(bin(n)))
941  for n in range(2**32 - 4096, 2**32):
942  assert rscan1(n) == len(bin(n)) - 1, (n, rscan1(n), len(bin(n)))
943  else:
944  print(debug.assertspeed_str(), end='')
945  print('ok'); sys.stdout.flush()
946 
947 
948  print('scan0()...', end=''); sys.stdout.flush()
949  assert scan0(0) == 0, scan0(0)
950  assert scan0(2**32 - 1) == 32, scan0(2**32 - 1)
951  for i in range(33):
952  assert scan0(2**i - 1) == i, (i, scan0(2**i - 1))
953  for n in range(32768):
954  if n&1 == 0:
955  assert scan0(n) == 0, (n, scan0(n))
956  else:
957  assert scan0(n) == scan0(n>>1) + 1, (n, scan0(n), scan0(n>>1))
958  if debug.assertspeed >= debug.ASSERT_NORMAL:
959  for n in range(1, 2**32, 1000000):
960  if n&1 == 0:
961  assert scan0(n) == 0, (n, scan0(n))
962  else:
963  assert scan0(n) == scan0(n>>1) + 1, (n, scan0(n), scan0(n>>1))
964  for n in range(2**32 - 32768, 2**32):
965  if n&1 == 0:
966  assert scan0(n) == 0, (n, scan0(n))
967  else:
968  assert scan0(n) == scan0(n>>1) + 1, (n, scan0(n), scan0(n>>1))
969  else:
970  print(debug.assertspeed_str(), end='')
971  print('ok'); sys.stdout.flush()
972 
973 
974  print('scan1()...', end=''); sys.stdout.flush()
975  assert scan1(0) == None, scan1(0)
976  for i in range(32):
977  assert scan1(2**i) == i, (i, scan1(2**i))
978  for n in range(1, 32768):
979  if n&1 == 1:
980  assert scan1(n) == 0, (n, scan1(n))
981  else:
982  assert scan1(n) == scan1(n>>1) + 1, (n, scan1(n), scan1(n>>1))
983  if debug.assertspeed >= debug.ASSERT_NORMAL:
984  for n in range(1, 2**32, 1000000):
985  if n&1 == 1:
986  assert scan1(n) == 0, (n, scan1(n))
987  else:
988  assert scan1(n) == scan1(n>>1) + 1, (n, scan1(n), scan1(n>>1))
989  for n in range(2**32 - 32768, 2**32):
990  if n&1 == 1:
991  assert scan1(n) == 0, (n, scan1(n))
992  else:
993  assert scan1(n) == scan1(n>>1) + 1, (n, scan1(n), scan1(n>>1))
994  else:
995  print(debug.assertspeed_str(), end='')
996  print('ok'); sys.stdout.flush()
997  debug.test_end()
998 
999  main_test()
1000 ##\endcond MAINTEST