Does Python allow access to some of the implementation details?

[Claudio Grondi]

Let's consider a test source code given at the very end of this posting.

The question is if Python allows somehow access to the bytes of the
representation of a long integer or integer in computers memory?
Or does Python hide such implementation details that deep, that there is
no way to get down to them?

The test code below shows, that extracting bits from an integer value n
is faster when using n&0x01 than when using n%2 and I suppose it is
because %2 tries to handle the entire integer, where &0x01 processes
only the last two bytes of it (I come to this because the speed
difference between &0x01 and %2 operations depends on how large the
value n is). If it were possible to 'tell' the %2 operation to operate
only on one short of the integer number representation there will be
probably no difference in speed. Is there a way to do this efficiently
in Python like it is possible in C when using pointers and recasting?

As I am on Python 2.4.2 and Microsoft Windows, I am interested in
details related to this Python version (to limit the scope of the
question).

Claudio

Here the code:

import time

# i = 2**25964951 - 1
i = 123456789**123
lstBitsModulo = []
start = time.clock()
while i:
i=i>>1
lstBitsModulo.append(i%2)
speedModulo = time.clock()-start

# i = 2**25964951 - 1
i = 123456789**123
lstBitsBitwiseAnd = []
start = time.clock()
while i:
i=i>>1
lstBitsBitwiseAnd.append(i&0x01)
speedBitwiseAnd = time.clock()-start

print
if lstBitsBitwiseAnd == lstBitsModulo :
print 'BitwiseAnd = %f '%(speedBitwiseAnd,)
print 'Modulo = %f '%(speedModulo,)

print # both lists are lists of long integer values
print lstBitsBitwiseAnd[0:3]
print lstBitsModulo[0:3]

[Diez B. Roggisch]

> The test code below shows, that extracting bits from an integer value n

is faster when using n&0x01 than when using n%2 and I suppose it is
because %2 tries to handle the entire integer, where &0x01 processes
only the last two bytes of it (I come to this because the speed
difference between &0x01 and %2 operations depends on how large the
value n is)

I doubt that the reason is in & handling less data. The reason is that % is
effectively a division, whereas & is a logical operation. Which have always
been _way_ faster than divisions.

Of course you are right that the bitfiddling _could_ be optimized when one
knows that only certain bytes of a number would be of interest. But I
seriously doubt that python does any optimization here. However, I don't
know for sure.

Regards,

Diez

[casevh]

I don't know of a way to directly access the internal structure of a
long, but you can speed up your example.

First, is the order of the commands

i=i>>1
lstBitsBitwiseAnd.append(i&0x01)

what you intend? The first low order bit is discarded because you've
done the shift first. And an extra 0 is appended.

If you are trying to get the binary representation of a long, try
i.__hex__(). This will create a string with the hex representation.
Conversion from hex to binary is left as an exercise for the reader. :-)

[Claudio Grondi]

ca****@comcast.net wrote:

I don't know of a way to directly access the internal structure of a
long, but you can speed up your example.

First, is the order of the commands

i=i>>1
lstBitsBitwiseAnd.append(i&0x01)

what you intend? The first low order bit is discarded because you've
done the shift first. And an extra 0 is appended.

If you are trying to get the binary representation of a long, try
i.__hex__(). This will create a string with the hex representation.
Conversion from hex to binary is left as an exercise for the reader. :-)

You are right, it is not correct if you want to get all bits out of an
integer value. I haven't payed attention to the proper order, because my
only intent was to check what is faster modulo-division or bitwise-and,
so for the outcome of this the order does not matter.

The i.__hex__() idea is very, very near to what I have originally asked
for. It's a pity, that it can't be generally considered faster than
usage of shifting+bitwise-and where the latter seem to be superior for
small long integers and integers (see attached code showing a break even
for integers which require more than appr. 16 up to 104 digits according
to multiple tests on my machine).

Claudio

import time

dctLstOfBitsVsCharOfNibble = {}
# dctLstOfBitsVsCharOfNibble is a dictionary with a key beeing one
character
# string representing hexadecimal value of a nibble and a value beeing a
list
# of bits of the nibble where the lowest bit is stored at index 0 of the
list.
# i.e.
dctLstOfBitsVsCharOfNibble = {
'0':[0, 0, 0, 0],
'1':[0, 0, 0, 1],
'2':[0, 0, 1, 0],
'3':[0, 0, 1, 1],
'4':[0, 1, 0, 0],
'5':[0, 1, 0, 1],
'6':[0, 1, 1, 0],
'7':[0, 1, 1, 1],
'8':[1, 0, 0, 0],
'9':[1, 0, 0, 1],
'A':[1, 0, 1, 0],
'B':[1, 0, 1, 1],
'C':[1, 1, 0, 0],
'D':[1, 1, 0, 1],
'E':[1, 1, 1, 0],
'F':[1, 1, 1, 1]
}
# The dictionary can also be generated e.g. using following code:
# dctLstOfBitsVsCharOfNibble = {}
# for intNibbleValue in range(0, 16):
# lstBitReprOfCurrNibble=[]
# for indxOfBit in range(0,4):
# lstBitReprOfCurrNibble.append(intNibbleValue>>indx OfBit&0x01)
# #:for
# lstBitReprOfCurrNibble.reverse()
#
dctLstOfBitsVsCharOfNibble['%X'%(intNibbleValue,)]=lstBitReprOfCurrNibble
# #:for

NoOf32bitChunksOfInteger = 0
n = 0
lstBitsBitwiseAnd = []
lstBitsModulo = []
lstBitsViaHex = []
timeBitwiseAnd = -1
timeModulo = -1
timeBitsViaHex = -1

while timeBitwiseAnd <= timeBitsViaHex:

n = (n<<32) + 0x12345678
NoOf32bitChunksOfInteger += 1

i = n
lstBitsModulo = []
start = time.clock()
while i:
lstBitsModulo.append(i%2)
i=i>>1
timeModulo = time.clock()-start

i = n
lstBitsBitwiseAnd = []
start = time.clock()
while i:
lstBitsBitwiseAnd.append(i&0x01)
i=i>>1
timeBitwiseAnd = time.clock()-start

i = n
# lstBitsViaHex = []
start = time.clock()
strHexOf_i = i.__hex__()[2:]
if strHexOf_i[-1]=='L':
strHexOf_i=strHexOf_i[0:-1]
#:if
intNoOfLeadingZeroBits = 0
lstBitsOfFirstNibble = dctLstOfBitsVsCharOfNibble[strHexOf_i[0]]
while not lstBitsOfFirstNibble[intNoOfLeadingZeroBits] and
intNoOfLeadingZeroBits < 4:
intNoOfLeadingZeroBits += 1
#:while
if intNoOfLeadingZeroBits == 4:
lstBitsViaHex = []
else:
lstBitsViaHex = lstBitsOfFirstNibble[intNoOfLeadingZeroBits:]
#:if
for indxToStrHexOf_i in range(1,len(strHexOf_i)):
lstBitsViaHex +=
dctLstOfBitsVsCharOfNibble[strHexOf_i[indxToStrHexOf_i]]
#:for
lstBitsViaHex.reverse()
timeBitsViaHex = time.clock()-start
#:while

if lstBitsBitwiseAnd == lstBitsModulo and lstBitsBitwiseAnd ==
lstBitsViaHex:
print
print ' Seconds for bit extraction from integer with %i hex-digits
when: '%(NoOf32bitChunksOfInteger*8,)
print
print ' looping over i>>1;i&0x01 = %f '%(timeBitwiseAnd,)
print ' looping over i>>1;i%%2 = %f '%(timeModulo,)
print ' using i.__hex__() repr. = %f '%(timeBitsViaHex,)
print
print ' For long integers i with number of hexadecimal digits '
print ' > %i '%(NoOf32bitChunksOfInteger*8,)
print ' bits extraction with i.__hex__() is faster then with
i>>1;i&0x01 .'
print
print ' Modulo division (%) is always much slower than bitwise and
(&). '

[Martin v. Löwis]

Claudio Grondi wrote:

The question is if Python allows somehow access to the bytes of the
representation of a long integer or integer in computers memory?

Not sure what you mean by "Python", and "allows" here. I allow you :-)

To do so, write a C file that is a Python module, and accesses the
internal representation of the long. Works super-fast.

You can get somewhat faster in Python than your code if you avoid
producing new long objects all the time, and do the task in chunks of 30
bits.

Regards,
Martin

import time

repeats = [None]*100

start = time.clock()
for repeat in repeats:
i = 123456789**123
lstBitsBitwiseAnd = []
while i:
lstBitsBitwiseAnd.append(i&0x01)
i=i>>1
print time.clock()-start

start = time.clock()
for repeat in repeats:
i = 123456789**123
lstBitsBitwiseAnd = []
done = False
while i:
i1 = int(i & 0x3FFFFFFF)
i >>= 30
if i == 0: done = True
for k in xrange(30):
lstBitsBitwiseAnd.append(i1 & 1)
i1 >>= 1
if done and i1==0:
# if this is the top word, and no bits are left,
# we are done
break
print time.clock()-start

[Claudio Grondi]

Martin v. Löwis wrote:

You can get somewhat faster in Python than your code if you avoid
producing new long objects all the time, and do the task in chunks of 30
bits. It would be nice if you could explain why you consider chunks of 30 bits
to be superior e.g. to chunks of 32 bits?
write a C file that is a Python module If I understand you right, there is no way to get direct access to
internal representation of Python objects by Python script language
means provided in the standard Python 2.4.2 distribution.
So the answer to the question in the subject is : NO (valid for what is
provided in the standard Python distribution, but not valid when
considering to write an own extension module in C)

Below an updated version of the previously posted code with included
code piece suggested by Martin v. Löwis.
The i.__hex__() method of bit extraction seem to be the best choice for
large (enough) integers, superior also to processing in chunks of 30
bits. Here an example of output resulting from run of below code on my
current machine:

Seconds for bit extraction from integer with 216 hex-digits when:

looping over i>>1;i&0x01 = 0.001227
^-- but in 32 bit chunks = 0.000685
looping over i>>1;i%2 = 0.001614
using i.__hex__() repr. = 0.000143

Bits extraction from long integers with number of hexadecimal digits 216

is at least 1 ms faster with i.__hex__() then with i>>1;i&0x01 method.

Modulo division (%2) is always slower than bitwise-and (&0x01).

It seems, that the __hex__() method wins on Pentium 4 3.0 GHz for any
value of integer, where on Pentium 4 2.8 GHz beginning with a given
value for long integers, but it could be, that this effect is caused by
the time measurement method used and not actually by the effect of using
another processor (sitting on identical motherboard).
This was the reason why I have decided to get at least 1 ms time
difference between the methods before printing the results (see code
below).

Claudio

import time

# dctLstOfBitsVsCharOfNibble is a dictionary with a key beeing one
character
# string representing hexadecimal value of a nibble and a value beeing a
list
# of bits of the nibble where the lowest bit is stored at index 0 of the
list.
# i.e.
dctLstOfBitsVsCharOfNibble = {
'0':[0, 0, 0, 0],
'1':[0, 0, 0, 1],
'2':[0, 0, 1, 0],
'3':[0, 0, 1, 1],
'4':[0, 1, 0, 0],
'5':[0, 1, 0, 1],
'6':[0, 1, 1, 0],
'7':[0, 1, 1, 1],
'8':[1, 0, 0, 0],
'9':[1, 0, 0, 1],
'A':[1, 0, 1, 0],
'B':[1, 0, 1, 1],
'C':[1, 1, 0, 0],
'D':[1, 1, 0, 1],
'E':[1, 1, 1, 0],
'F':[1, 1, 1, 1]
}
# The dctLstOfBitsVsCharOfNibble dictionary can be generated by
following code:
# dctLstOfBitsVsCharOfNibble = {}
# for intNibbleValue in range(0, 16):
# lstBitReprOfCurrNibble=[]
# for indxOfBit in range(0,4):
# lstBitReprOfCurrNibble.append(intNibbleValue>>indx OfBit&0x01)
# #:for
# lstBitReprOfCurrNibble.reverse()
#
dctLstOfBitsVsCharOfNibble['%X'%(intNibbleValue,)]=lstBitReprOfCurrNibble
# #:for
n = 0
NoOf32bitChunks = 0
lstBitsBitwiseAnd = []
lstBitsModulo = []
lstViaBitChunks = []
lstBitsViaHex = []
timeBitwiseAnd = -1
timeModulo = -1
timeBitsViaHex = -1
timeViaBitChunks = -1

bitChunkSize = 32 # must be <= 32

while timeBitwiseAnd <= timeBitsViaHex + 0.001:

n = (n<<32) + 0x12345678

NoOf32bitChunks += 1

i = n
lstBitsModulo = []
start = time.clock()
while i:
lstBitsModulo.append(i%2)
i=i>>1
timeModulo = time.clock()-start

i = n
lstBitsBitwiseAnd = []
start = time.clock()
while i:
lstBitsBitwiseAnd.append(i&0x01)
i=i>>1
timeBitwiseAnd = time.clock()-start

i = n
lstViaBitChunks = []
bitFilter = 0
for dummy in range(bitChunkSize):
bitFilter = (bitFilter<<1)+1
#:for

start = time.clock()
done = False
while i:
i1 = int(i & bitFilter)
i >>= bitChunkSize
if i == 0: done = True
for k in xrange(bitChunkSize):
lstViaBitChunks.append(i1 & 1)
i1 >>= 1
if done and i1==0:
# if this is the top word, and no bits are left, we are done
break
#:if
#:for
#:while
timeViaBitChunks = time.clock()-start

i = n
# lstBitsViaHex = []
start = time.clock()
strHexOf_i = i.__hex__()[2:]
if strHexOf_i[-1]=='L':
strHexOf_i=strHexOf_i[0:-1]
#:if
intNoOfLeadingZeroBits = 0
lstBitsOfFirstNibble = dctLstOfBitsVsCharOfNibble[strHexOf_i[0]]
while not lstBitsOfFirstNibble[intNoOfLeadingZeroBits] and
intNoOfLeadingZeroBits < 4:
intNoOfLeadingZeroBits += 1
#:while
if intNoOfLeadingZeroBits == 4:
lstBitsViaHex = []
else:
lstBitsViaHex = lstBitsOfFirstNibble[intNoOfLeadingZeroBits:]
#:if
for indxToStrHexOf_i in range(1,len(strHexOf_i)):
lstBitsViaHex +=
dctLstOfBitsVsCharOfNibble[strHexOf_i[indxToStrHexOf_i]]
#:for
lstBitsViaHex.reverse()
timeBitsViaHex = time.clock()-start
#:while

if( lstBitsBitwiseAnd == lstBitsModulo
and lstBitsBitwiseAnd == lstBitsViaHex
and lstBitsBitwiseAnd == lstViaBitChunks ):
print
print ' Seconds for bit extraction from integer with %i hex-digits
when: '%(NoOf32bitChunks*8,)
print
print ' looping over i>>1;i&0x01 = %f '%(timeBitwiseAnd,)
print ' ^-- but in %i bit chunks = %f '%(bitChunkSize,
timeViaBitChunks)
print ' looping over i>>1;i%%2 = %f '%(timeModulo,)
print ' using i.__hex__() repr. = %f '%(timeBitsViaHex,)
print
print ' Bits extraction from long integers with number of
hexadecimal digits '
print ' > %i '%(NoOf32bitChunks*8,)
print ' is at least 1 ms faster with i.__hex__() then with
i>>1;i&0x01 method.'
print
print ' Modulo division (%2) is always slower than bitwise-and (&0x01).'

[Paul Rubin]

Claudio Grondi <cl************@freenet.de> writes:

The question is if Python allows somehow access to the bytes of the
representation of a long integer or integer in computers memory?
No it doesn't, and that's a good thing, since the internal
representation is a little bit surprising (it stores 15 bits of the
long int in each 16-bit word of the representation, to make the
arithmetic routines a little simpler).
If it were possible to 'tell' the %2 operation to operate
only on one short of the integer number representation there will be
probably no difference in speed. Is there a way to do this efficiently
in Python like it is possible in C when using pointers and recasting?

The usual trick to get at the contents of a long is to use hex
conversion and maybe the array module (untested):

a = '%x' % n
if len(a) % 2 == 1:
a = '0' + a
s = array.array('B', binascii.unhexlify(a))

s now gives you the individual bytes of n.

[Tim Peters]

[Claudio Grondi]

Let's consider a test source code given at the very end of this posting.

The question is if Python allows somehow access to the bytes of the
representation of a long integer or integer in computers memory?
CPython does not expose its internal representation of longs at the
Python level.
Or does Python hide such implementation details that deep, that there is
no way to get down to them?
As above.
The test code below shows, that extracting bits from an integer value n
is faster when using n&0x01 than when using n%2 and I suppose it is
because %2 tries to handle the entire integer,
It not only tries, it succeeds ;-)
where &0x01 processes only the last two bytes of it
If x and y are positive longs, the time required to compute x&y in all
recent CPythons is essentially proportional to the number of bits in
min(x, y).
...
If it were possible to 'tell' the %2 operation to operate only on one short of
the integer number representation there will be probably no difference in
speed. Is there a way to do this efficiently in Python like it is possible in
C when using pointers and recasting?
No.
As I am on Python 2.4.2 and Microsoft Windows, I am interested in
details related to this Python version (to limit the scope of the
question).

Doesn't really matter: same answers for all recent versions of
CPython on all platforms. If you go back far enough, in older
versions of CPython the time to compute x&y was proportional to the
number of bits in max(x, y) (instead of min(x, y)).

[mensanator]

Claudio Grondi wrote:

Martin v. Löwis wrote:

You can get somewhat faster in Python than your code if you avoid
producing new long objects all the time, and do the task in chunks of 30
bits.

It would be nice if you could explain why you consider chunks of 30 bits
to be superior e.g. to chunks of 32 bits?

write a C file that is a Python module

If I understand you right, there is no way to get direct access to
internal representation of Python objects by Python script language
means provided in the standard Python 2.4.2 distribution.
So the answer to the question in the subject is : NO (valid for what is
provided in the standard Python distribution, but not valid when
considering to write an own extension module in C)

No need to re-invent the wheel. That extension has already been
written. The GMPY module has a full suite of bit-functions:

digits(...)
digits(x[,base]): returns Python string representing x in the
given base (2 to 36, default 10 if omitted or 0); leading '-'
present if x<0, but no leading '+' if x>=0. x must be an mpz,
or else gets coerced into one.

getbit(...)
getbit(x,n): returns 0 or 1, the bit-value of bit n of x;
n must be an ordinary Python int, >=0; x is an mpz, or else
gets coerced to one.

hamdist(...)
hamdist(x,y): returns the Hamming distance (number of bit-positions
where the bits differ) between x and y. x and y must be mpz,
or else get coerced to mpz.

lowbits(...)
lowbits(x,n): returns the n lowest bits of x; n must be an
ordinary Python int, >0; x must be an mpz, or else gets
coerced to one.

numdigits(...)
numdigits(x[,base]): returns length of string representing x in
the given base (2 to 36, default 10 if omitted or 0); the value
returned may sometimes be 1 more than necessary; no provision
for any 'sign' characte, nor leading '0' or '0x' decoration,
is made in the returned length. x must be an mpz, or else gets
coerced into one.

popcount(...)
popcount(x): returns the number of 1-bits set in x; note that
this is 'infinite' if x<0, and in that case, -1 is returned.
x must be an mpz, or else gets coerced to one.

scan0(...)
scan0(x, n=0): returns the bit-index of the first 0-bit of x (that
is at least n); n must be an ordinary Python int, >=0. If no more
0-bits are in x at or above bit-index n (which can only happen for
x<0, notionally extended with infinite 1-bits), None is returned.
x must be an mpz, or else gets coerced to one.

scan1(...)
scan1(x, n=0): returns the bit-index of the first 1-bit of x (that
is at least n); n must be an ordinary Python int, >=0. If no more
1-bits are in x at or above bit-index n (which can only happen for
x>=0, notionally extended with infinite 0-bits), None is returned.
x must be an mpz, or else gets coerced to one.

setbit(...)
setbit(x,n,v=1): returns a copy of the value of x, with bit n set
to value v; n must be an ordinary Python int, >=0; v, 0 or !=0;
x must be an mpz, or else gets coerced to one.

By using the scan1 function, I can run rings around the BitwiseAnd
(using the program from your first post, correcting the missing bit
problem):

BitwiseAnd = 0.438082
Modulo = 2.576335
GMPY = 0.109865

33170 bits BitwiseAnd 1-bits: 16590
33170 bits Modulo 1-bits: 16590
33170 bits GMPY 1-bits: 16590

For BitwiseAnd and Modulo the 1-bit counts were found by
summing the lists. For GMPY, I used the popcount function.

You can get Windows binaries for GMPY at

<http://home.comcast.net/~casevh/>
import time
import gmpy

# i = 2**25964951 - 1
i = 123456789**1234
lstBitsModulo = []
start = time.clock()
while i:
lstBitsModulo.append(i%2)
i=i>>1
speedModulo = time.clock()-start

# i = 2**25964951 - 1
i = 123456789**1234
lstBitsBitwiseAnd = []
start = time.clock()
while i:
lstBitsBitwiseAnd.append(i&0x01)
i=i>>1
speedBitwiseAnd = time.clock()-start

i = gmpy.mpz(123456789**1234)
lstBitsGMPY = []
start = time.clock()
f = gmpy.scan1(i,0)
if f==0:
lstBitsGMPY.append(1)
k = 1
f = gmpy.scan1(i,1)
else:
k = 0
while f:
while k<f:
lstBitsGMPY.append(0)
k += 1
lstBitsGMPY.append(1)
k += 1
f = gmpy.scan1(i,f+1)
speedGMPY = time.clock()-start
print
if lstBitsBitwiseAnd == lstBitsModulo :
print 'BitwiseAnd = %f '%(speedBitwiseAnd,)
print 'Modulo = %f '%(speedModulo,)
print 'GMPY = %f '%(speedGMPY,)

print # both lists are lists of long integer values
print len(lstBitsBitwiseAnd),'bits BitwiseAnd
1-bits:',sum(lstBitsBitwiseAnd)
print len(lstBitsModulo), 'bits Modulo
1-bits:',sum(lstBitsModulo)
print len(lstBitsGMPY), 'bits GMPY
1-bits:',gmpy.popcount(i)

[Claudio Grondi]

me********@aol.com wrote:

Claudio Grondi wrote:

Martin v. Löwis wrote:

You can get somewhat faster in Python than your code if you avoid
producing new long objects all the time, and do the task in chunks of 30
bits.

It would be nice if you could explain why you consider chunks of 30 bits
to be superior e.g. to chunks of 32 bits?

write a C file that is a Python module

If I understand you right, there is no way to get direct access to
internal representation of Python objects by Python script language
means provided in the standard Python 2.4.2 distribution.
So the answer to the question in the subject is : NO (valid for what is
provided in the standard Python distribution, but not valid when
considering to write an own extension module in C)

No need to re-invent the wheel. That extension has already been
written. The GMPY module has a full suite of bit-functions:

digits(...)
digits(x[,base]): returns Python string representing x in the
given base (2 to 36, default 10 if omitted or 0); leading '-'
present if x<0, but no leading '+' if x>=0. x must be an mpz,
or else gets coerced into one.

That's nice function. A pity it's not in the standard Python distro as
the inversion of the int() operation.
What I am also looking for is a conversion to base 256 (i.e where the
full byte is used and the string and the integer have the same actual
content if on appropriate endian machine), which would make the bit
extraction comparable easy and effective as the i.__hex__() based method.
Using digits() instead of the code you have provided speeds the whole
thing up two times (see attached code for details), but still is
i.__hex__() the best way to go and could be improved probably only by
direct conversion to base 256 or even higher base as e.g. 2**16 or 2**32.

Claudio

import time

# dctLstOfBitsVsCharOfNibble is a dictionary with a key beeing one
character
# string representing hexadecimal value of a nibble and a value beeing a
list
# of bits of the nibble where the lowest bit is stored at index 0 of the
list.
# i.e.
dctLstOfBitsVsCharOfNibble = {
'0':[0, 0, 0, 0],
'1':[0, 0, 0, 1],
'2':[0, 0, 1, 0],
'3':[0, 0, 1, 1],
'4':[0, 1, 0, 0],
'5':[0, 1, 0, 1],
'6':[0, 1, 1, 0],
'7':[0, 1, 1, 1],
'8':[1, 0, 0, 0],
'9':[1, 0, 0, 1],
'A':[1, 0, 1, 0],
'B':[1, 0, 1, 1],
'C':[1, 1, 0, 0],
'D':[1, 1, 0, 1],
'E':[1, 1, 1, 0],
'F':[1, 1, 1, 1]
}
# The dctLstOfBitsVsCharOfNibble dictionary can be generated by
following code:
# dctLstOfBitsVsCharOfNibble = {}
# for intNibbleValue in range(0, 16):
# lstBitReprOfCurrNibble=[]
# for indxOfBit in range(0,4):
# lstBitReprOfCurrNibble.append(intNibbleValue>>indx OfBit&0x01)
# #:for
# lstBitReprOfCurrNibble.reverse()
#
dctLstOfBitsVsCharOfNibble['%X'%(intNibbleValue,)]=lstBitReprOfCurrNibble
# #:for
n = 0
NoOf32bitChunks = 0
lstBitsBitwiseAnd = []
lstBitsModulo = []
lstViaBitChunks = []
lstBitsViaHex = []
lstBitsGMPY = []
timeBitwiseAnd = -1
timeModulo = -1
timeBitsViaHex = -1
timeViaBitChunks = -1
timeGMPY = -1

bitChunkSize = 32 # must be <= 32

while timeBitwiseAnd <= timeBitsViaHex + 0.001:

n = (n<<32) + 0x12345678

NoOf32bitChunks += 1

i = n
lstBitsModulo = []
start = time.clock()
while i:
lstBitsModulo.append(i%2)
i=i>>1
timeModulo = time.clock()-start

i = n
lstBitsBitwiseAnd = []
start = time.clock()
while i:
lstBitsBitwiseAnd.append(i&0x01)
i=i>>1
timeBitwiseAnd = time.clock()-start

i = n
lstViaBitChunks = []
bitFilter = 0
for dummy in range(bitChunkSize):
bitFilter = (bitFilter<<1)+1
#:for

start = time.clock()
done = False
while i:
i1 = int(i & bitFilter) # int() converts here a long-integer to integer
i >>= bitChunkSize
if i == 0: done = True
for k in xrange(bitChunkSize):
lstViaBitChunks.append(i1 & 1)
i1 >>= 1
if done and i1==0:
# if this is the top word, and no bits are left, we are done
break
#:if
#:for
#:while
timeViaBitChunks = time.clock()-start

i = n
# lstBitsViaHex = []
start = time.clock()
strHexOf_i = i.__hex__()[2:]
if strHexOf_i[-1]=='L':
strHexOf_i=strHexOf_i[0:-1]
#:if
intNoOfLeadingZeroBits = 0
lstBitsOfFirstNibble = dctLstOfBitsVsCharOfNibble[strHexOf_i[0]]
while not lstBitsOfFirstNibble[intNoOfLeadingZeroBits] and
intNoOfLeadingZeroBits < 4:
intNoOfLeadingZeroBits += 1
#:while
if intNoOfLeadingZeroBits == 4:
lstBitsViaHex = []
else:
lstBitsViaHex = lstBitsOfFirstNibble[intNoOfLeadingZeroBits:]
#:if
for indxToStrHexOf_i in range(1,len(strHexOf_i)):
lstBitsViaHex +=
dctLstOfBitsVsCharOfNibble[strHexOf_i[indxToStrHexOf_i]]
#:for
lstBitsViaHex.reverse()
timeBitsViaHex = time.clock()-start

import gmpy
lstBitsGMPY = []
# start = time.clock()
# i = gmpy.mpz(n)
# f = gmpy.scan1(i,0)
# if f==0:
# lstBitsGMPY.append(1)
# k = 1
# f = gmpy.scan1(i,1)
# else:
# k = 0
# while f:
# while k<f:
# lstBitsGMPY.append(0)
# k += 1
# lstBitsGMPY.append(1)
# k += 1
# f = gmpy.scan1(i,f+1)
# timeGMPY = time.clock()-start
start = time.clock()
i = gmpy.mpz(n)
strBitsOf_i = gmpy.digits(i,2)
for char in strBitsOf_i:
if char=='0':
lstBitsGMPY.append(0)
else:
lstBitsGMPY.append(1)
#:for
lstBitsGMPY.reverse()
timeGMPY = time.clock()-start

#:while

if( lstBitsBitwiseAnd == lstBitsModulo
and lstBitsBitwiseAnd == lstBitsViaHex
and lstBitsBitwiseAnd == lstViaBitChunks
and lstBitsBitwiseAnd == lstBitsGMPY):
print
print ' Seconds for bit extraction from integer with %i hex-digits
when: '%(NoOf32bitChunks*8,)
print
print ' looping over i>>1;i&0x01 = %f '%(timeBitwiseAnd,)
print ' ^-- but in %i bit chunks = %f '%(bitChunkSize,
timeViaBitChunks)
print ' looping over i>>1;i%%2 = %f '%(timeModulo,)
print ' using i.__hex__() repr. = %f '%(timeBitsViaHex,)
print ' using gmpy.digits(i,2) = %f '%(timeGMPY,)
print
print ' Bits extraction from long integers with number of
hexadecimal digits '
print ' > %i '%(NoOf32bitChunks*8,)
print ' is at least 1 ms faster with i.__hex__() then with
i>>1;i&0x01 method.'
print
print ' Modulo division (%2) is always slower than bitwise-and (&0x01).'

[Martin v. Löwis]

Claudio Grondi wrote:

You can get somewhat faster in Python than your code if you avoid
producing new long objects all the time, and do the task in chunks of 30
bits.

It would be nice if you could explain why you consider chunks of 30 bits
to be superior e.g. to chunks of 32 bits?

With chunks of 32 bits, you might get negative numbers. Then,
right-shifting bit-by-bit will never get you to zero.

It also happens that the long ints are represented as arrays of
15-bit values, so that the shift by 30 *could* be implemented
without shifts in the individual words; however, this optimization
is not done.

Regards,
Martin

[Alex Martelli]

Claudio Grondi <cl************@freenet.de> wrote:
...

What I am also looking for is a conversion to base 256 (i.e where the
full byte is used and the string and the integer have the same actual
content if on appropriate endian machine), which would make the bit
gmpy supplies that, too:

gmpy.binary(x) or x.binary(): returns a portable binary
representation (base-256 little endian) of an mpz object, suitable
for saving into a file (or db, whatever) -- this string can later
be passed as the first argument to function gmpy.mpz (with a
second argument with value 256) to reconstruct a copy of the
original mpz object.
extraction comparable easy and effective as the i.__hex__() based method.

I suspect bit-extraction is still going to be faster with getbit and
friends, but I'm sure you can measure that for yourself (I'm stuck with
a loaner machine these days, and don't currently have gmpy at hand).
Alex

[Claudio Grondi]

Paul Rubin wrote:

Claudio Grondi <cl************@freenet.de> writes:

The question is if Python allows somehow access to the bytes of the
representation of a long integer or integer in computers memory?

No it doesn't, and that's a good thing, since the internal
representation is a little bit surprising (it stores 15 bits of the
long int in each 16-bit word of the representation, to make the
arithmetic routines a little simpler).

If it were possible to 'tell' the %2 operation to operate
only on one short of the integer number representation there will be
probably no difference in speed. Is there a way to do this efficiently
in Python like it is possible in C when using pointers and recasting?

The usual trick to get at the contents of a long is to use hex
conversion and maybe the array module (untested):

a = '%x' % n
if len(a) % 2 == 1:
a = '0' + a
s = array.array('B', binascii.unhexlify(a))

s now gives you the individual bytes of n.

This is the _fastest_ approach I have seen so far (updated code attached).
Thank you!

Claudio

import time

# dctLstOfBitsVsCharOfNibble is a dictionary with a key beeing one
character
# string representing hexadecimal value of a nibble and a value beeing a
list
# of bits of the nibble where the lowest bit is stored at index 0 of the
list.
# i.e.
dctLstOfBitsVsCharOfNibble = {
'0':[0, 0, 0, 0],
'1':[0, 0, 0, 1],
'2':[0, 0, 1, 0],
'3':[0, 0, 1, 1],
'4':[0, 1, 0, 0],
'5':[0, 1, 0, 1],
'6':[0, 1, 1, 0],
'7':[0, 1, 1, 1],
'8':[1, 0, 0, 0],
'9':[1, 0, 0, 1],
'A':[1, 0, 1, 0],
'B':[1, 0, 1, 1],
'C':[1, 1, 0, 0],
'D':[1, 1, 0, 1],
'E':[1, 1, 1, 0],
'F':[1, 1, 1, 1]
}
# The dctLstOfBitsVsCharOfNibble dictionary can be also generated by
following code:
# dctLstOfBitsVsCharOfNibble = {}
# for intNibbleValue in range(0, 16):
# lstBitReprOfCurrNibble=[]
# for indxOfBit in range(0,4):
# lstBitReprOfCurrNibble.append(intNibbleValue>>indx OfBit&0x01)
# #:for
# lstBitReprOfCurrNibble.reverse()
#
dctLstOfBitsVsCharOfNibble['%X'%(intNibbleValue,)]=lstBitReprOfCurrNibble
# #:for

dctLstOfBitsVsOrdOfChar = {}
for ordOfChar in range(256):
dctLstOfBitsVsOrdOfChar[ordOfChar] =
dctLstOfBitsVsCharOfNibble['%X'%(ordOfChar>>4,)] +
dctLstOfBitsVsCharOfNibble['%X'%(ordOfChar&0x0F,)]
#:for
# what gives: {
# 0x00:[0, 0, 0, 0, 0, 0, 0, 0],
# 0x01:[0, 0, 0, 0, 0, 0, 0, 1],
# 0x02:[0, 0, 0, 0, 0, 0, 1, 0],
# ...
# 0xFD:[1, 1, 1, 1, 1, 1, 0, 1],
# 0xFE:[1, 1, 1, 1, 1, 1, 1, 0],
# 0xFF:[1, 1, 1, 1, 1, 1, 1, 1]
# }

n = 0
NoOf32bitChunks = 0
lstBitsBitwiseAnd = []
lstBitsModulo = []
lstViaBitChunks = []
lstBitsViaHex = []
lstBitsGMPY = []
lstViaHexAndArray = []
timeBitwiseAnd = -1
timeModulo = -1
timeBitsViaHex = -1
timeViaBitChunks = -1
timeGMPY = -1
timeViaHexAndArray = -1

bitChunkSize = 32 # must be <= 32

while timeBitwiseAnd <= timeBitsViaHex + 0.001:

n = (n<<32) + 0x12345678

NoOf32bitChunks += 1

i = n
lstBitsModulo = []
start = time.clock()
while i:
lstBitsModulo.append(i%2)
i=i>>1
timeModulo = time.clock()-start

i = n
lstBitsBitwiseAnd = []
start = time.clock()
while i:
lstBitsBitwiseAnd.append(i&0x01)
i=i>>1
timeBitwiseAnd = time.clock()-start

i = n
lstViaBitChunks = []
bitFilter = 0
for dummy in range(bitChunkSize):
bitFilter = (bitFilter<<1)+1
#:for

start = time.clock()
done = False
while i:
i1 = int(i & bitFilter) # int() converts here a long-integer to integer
i >>= bitChunkSize
if i == 0: done = True
for k in xrange(bitChunkSize):
lstViaBitChunks.append(i1 & 1)
i1 >>= 1
if done and i1==0:
# if this is the top word, and no bits are left, we are done
break
#:if
#:for
#:while
timeViaBitChunks = time.clock()-start

i = n
# lstBitsViaHex = []
start = time.clock()
strHexOf_i = i.__hex__()[2:]
if strHexOf_i[-1]=='L':
strHexOf_i=strHexOf_i[0:-1]
#:if
intNoOfLeadingZeroBits = 0
lstBitsOfFirstNibble = dctLstOfBitsVsCharOfNibble[strHexOf_i[0]]
while not lstBitsOfFirstNibble[intNoOfLeadingZeroBits] and
intNoOfLeadingZeroBits < 4:
intNoOfLeadingZeroBits += 1
#:while
if intNoOfLeadingZeroBits == 4:
lstBitsViaHex = []
else:
lstBitsViaHex = lstBitsOfFirstNibble[intNoOfLeadingZeroBits:]
#:if
for indxToStrHexOf_i in range(1,len(strHexOf_i)):
lstBitsViaHex +=
dctLstOfBitsVsCharOfNibble[strHexOf_i[indxToStrHexOf_i]]
#:for
lstBitsViaHex.reverse()
timeBitsViaHex = time.clock()-start

i = n
lstViaHexAndArray = []
import array, binascii
start = time.clock()
strHexOf_i = i.__hex__()[2:]
if strHexOf_i[-1]=='L':
strHexOf_i=strHexOf_i[0:-1]
#:if
for item in array.array('B', binascii.unhexlify(strHexOf_i)):
lstViaHexAndArray += dctLstOfBitsVsOrdOfChar[item]
#:for
intNoOfLeadingZeroBits = 0
while not lstViaHexAndArray[intNoOfLeadingZeroBits] and
intNoOfLeadingZeroBits < 4:
intNoOfLeadingZeroBits += 1
#:while
if intNoOfLeadingZeroBits == 4:
lstViaHexAndArray = []
else:
lstViaHexAndArray = lstViaHexAndArray[intNoOfLeadingZeroBits:]
#:if
lstViaHexAndArray.reverse()
timeViaHexAndArray = time.clock()-start

import gmpy
lstBitsGMPY = []
# start = time.clock()
# i = gmpy.mpz(n)
# f = gmpy.scan1(i,0)
# if f==0:
# lstBitsGMPY.append(1)
# k = 1
# f = gmpy.scan1(i,1)
# else:
# k = 0
# while f:
# while k<f:
# lstBitsGMPY.append(0)
# k += 1
# lstBitsGMPY.append(1)
# k += 1
# f = gmpy.scan1(i,f+1)
# timeGMPY = time.clock()-start
start = time.clock()
i = gmpy.mpz(n)
strBitsOf_i = gmpy.digits(i,2)
for char in strBitsOf_i:
if char=='0':
lstBitsGMPY.append(0)
else:
lstBitsGMPY.append(1)
#:for
lstBitsGMPY.reverse()
timeGMPY = time.clock()-start

#:while

if( lstBitsBitwiseAnd == lstBitsModulo
and lstBitsBitwiseAnd == lstBitsViaHex
and lstBitsBitwiseAnd == lstViaBitChunks
and lstBitsBitwiseAnd == lstBitsGMPY
and lstBitsBitwiseAnd == lstViaHexAndArray):
print
print ' Seconds for bit extraction from integer with %i hex-digits
when: '%(NoOf32bitChunks*8,)
print
print ' looping over i>>1;i&0x01 = %f '%(timeBitwiseAnd,)
print ' ^-- but in %i bit chunks = %f '%(bitChunkSize,
timeViaBitChunks)
print ' looping over i>>1;i%%2 = %f '%(timeModulo,)
print ' using i.__hex__() repr. = %f '%(timeBitsViaHex,)
print ' using __hex__,array,binascii = %f '%(timeViaHexAndArray,)
print ' using gmpy.digits(i,2) = %f '%(timeGMPY,)
print
print ' Bits extraction from long integers with number of
hexadecimal digits '
print ' > %i '%(NoOf32bitChunks*8,)
print ' is at least 1 ms faster with i.__hex__() then with
i>>1;i&0x01 method.'
print
print ' Modulo division (%2) is always slower than bitwise-and (&0x01).'

[Carl Friedrich Bolz]

Paul Rubin wrote:

Claudio Grondi <cl************@freenet.de> writes:

The question is if Python allows somehow access to the bytes of the
representation of a long integer or integer in computers memory?

No it doesn't, and that's a good thing, since the internal
representation is a little bit surprising (it stores 15 bits of the
long int in each 16-bit word of the representation, to make the
arithmetic routines a little simpler).

Indeed. There are even more reasons why this is a Good Thing (tm) (not
only because the internal representation is surprising). Basically it
gives the implementor of a Python interpreter the freedom to choose the
internal representation that he deems to be the most fitting. If
implementation details leaked outside that wouldn't be possible anymore.

Cheers,

Carl Friedrich Bolz

[Bengt Richter]

On Sat, 07 Jan 2006 14:05:18 +0100, Claudio Grondi <cl************@freenet.de> wrote:
[...]

What I am also looking for is a conversion to base 256 (i.e where the
full byte is used and the string and the integer have the same actual
content if on appropriate endian machine), which would make the bit
extraction comparable easy and effective as the i.__hex__() based method.
Using digits() instead of the code you have provided speeds the whole
thing up two times (see attached code for details), but still is
i.__hex__() the best way to go and could be improved probably only by
direct conversion to base 256 or even higher base as e.g. 2**16 or 2**32.

(see Paul Rubin's post first).
BTW, I'd bet that '%x'.__mod__(i) will save you time over i.__hex__() by the time
you finish fiddling with 0x and L, even if you don't use the rest.

The question looming is, "What are you intending to do with your new representations
of twos complement integers?"

BTW2, an easy way to play with integers chopped into little-endian bit field sequences is
a generator, e.g., (note that last field is sign bits, either all zeroes or all ones, so
you can unambiguously reconstruct a signed integer from this variable width representation).
(not very tested, and BTW as you see I hacked in using int when possible for return values)

def bitsof(n, width=8): ... m = (2**(width-1)-1)*2+1 # allow 2**width-1 == sys.maxint as int
... if type(m) is long:
... yield n&m
... while n>0 or n<-1:
... n>>=width
... yield n&m
... else:
... yield int(n&m)
... while n>0 or n<-1:
... n>>=width
... yield int(n&m)
... list(bitsof(11,1)) [1, 1, 0, 1, 0] list(bitsof(5,1)) [1, 0, 1, 0] list(bitsof(-5,1)) [1, 1, 0, 1] hex(3**100) '0x5A4653CA673768565B41F775D6947D55CF3813D1L' ''.join(map('%02X'.__mod__, bitsof(3**100, 8))[::-1]) '005A4653CA673768565B41F775D6947D55CF3813D1' ''.join(map('%02X'.__mod__, bitsof(-3**100, 8))[::-1]) 'FFA5B9AC3598C897A9A4BE088A296B82AA30C7EC2F' hex(-3**100)

'-0x5A4653CA673768565B41F775D6947D55CF3813D1L'

<gentle rant>
(I leave it to your judgement as to how useful our current hex() representation
of negative numebers is ;-)
</gentle rant>

Regards,
Bengt Richter

[Claudio Grondi]

Bengt Richter wrote:

On Sat, 07 Jan 2006 14:05:18 +0100, Claudio Grondi <cl************@freenet.de> wrote:
[...]

What I am also looking for is a conversion to base 256 (i.e where the
full byte is used and the string and the integer have the same actual
content if on appropriate endian machine), which would make the bit
extraction comparable easy and effective as the i.__hex__() based method.
Using digits() instead of the code you have provided speeds the whole
thing up two times (see attached code for details), but still is
i.__hex__() the best way to go and could be improved probably only by
direct conversion to base 256 or even higher base as e.g. 2**16 or 2**32.

(see Paul Rubin's post first).
BTW, I'd bet that '%x'.__mod__(i) will save you time over i.__hex__() by the time
you finish fiddling with 0x and L, even if you don't use the rest.

Yes, it seem to do, but not very significant, at least in case of the
code provided (see attachment). Here the output of run of provided code
on my Pentium 4, 3.0 GHz :
Seconds for bit extraction from integer with 280 hex-digits when:
looping over i>>1;i&0x01 = 0.001207
^-- but in 30 bit chunks = 0.000904
looping over i>>1;i%2 = 0.002409
using i.__hex__() repr. = 0.000186
using '%02X'.__mod__(i) = 0.000145
using __hex__,array,binascii = 0.000117
using __mod__,array,binascii = 0.000114
using gmpy.digits(i,2) = 0.000615
The question looming is, "What are you intending to do with your new representations
of twos complement integers?" As you see in the 'Subject' I am currently not primary after conversion
of integers, but after understanding of Python implementation. The code
posted is a kind of side effect required in order to be able to
demonstrate progress if any.
What I have lately learned from this and some other threads in
(de.)comp.lang.python is, that to be able to get the best out of Python
in terms of speed and understanding what is or is not possible, it is
vital and necessary to understand the implementation.
Another reason behind this all is, that I was so impressed as it had
turned out, that it was possible to get the CPU time required for
conversion of the largest known prime to decimal form down from six
hours to six seconds (using BigDec), that I am now step by step checking
if similar effects can't be achieved also elsewhere.

BTW2, an easy way to play with integers chopped into little-endian bit field sequences is
a generator, e.g., (note that last field is sign bits, either all zeroes or all ones, so
you can unambiguously reconstruct a signed integer from this variable width representation).
(not very tested, and BTW as you see I hacked in using int when possible for return values)

>>> def bitsof(n, width=8): ... m = (2**(width-1)-1)*2+1 # allow 2**width-1 == sys.maxint as int
... if type(m) is long:
... yield n&m
... while n>0 or n<-1:
... n>>=width
... yield n&m
... else:
... yield int(n&m)
... while n>0 or n<-1:
... n>>=width
... yield int(n&m)
... >>> list(bitsof(11,1)) [1, 1, 0, 1, 0] >>> list(bitsof(5,1)) [1, 0, 1, 0] >>> list(bitsof(-5,1)) [1, 1, 0, 1] >>> hex(3**100) '0x5A4653CA673768565B41F775D6947D55CF3813D1L' >>> ''.join(map('%02X'.__mod__, bitsof(3**100, 8))[::-1]) '005A4653CA673768565B41F775D6947D55CF3813D1' >>> ''.join(map('%02X'.__mod__, bitsof(-3**100, 8))[::-1]) 'FFA5B9AC3598C897A9A4BE088A296B82AA30C7EC2F' >>> hex(-3**100)

'-0x5A4653CA673768565B41F775D6947D55CF3813D1L'

<gentle rant>
(I leave it to your judgement as to how useful our current hex() representation
of negative numebers is ;-)
</gentle rant>

Regards,
Bengt Richter

I haven't yet run into negative integers, so thank's for making me aware
of the potential problems with it. Yes, I would not expect the hex() to
give me the minus sign - I see I should be very careful here (this is
also the reason why I generally try to avoid usage of negative integers
as good as I can).

Claudio

P.S. Attachment:

import time

# dctLstOfBitsVsCharOfNibble is a dictionary with a key beeing one
character
# string representing hexadecimal value of a nibble and a value beeing a
list
# of bits of the nibble where the lowest bit is stored at index 0 of the
list.
# i.e.
dctLstOfBitsVsCharOfNibble = {
'0':[0, 0, 0, 0],
'1':[0, 0, 0, 1],
'2':[0, 0, 1, 0],
'3':[0, 0, 1, 1],
'4':[0, 1, 0, 0],
'5':[0, 1, 0, 1],
'6':[0, 1, 1, 0],
'7':[0, 1, 1, 1],
'8':[1, 0, 0, 0],
'9':[1, 0, 0, 1],
'A':[1, 0, 1, 0],
'B':[1, 0, 1, 1],
'C':[1, 1, 0, 0],
'D':[1, 1, 0, 1],
'E':[1, 1, 1, 0],
'F':[1, 1, 1, 1]
}
# The dctLstOfBitsVsCharOfNibble dictionary can be also generated by
following code:
# dctLstOfBitsVsCharOfNibble = {}
# for intNibbleValue in range(0, 16):
# lstBitReprOfCurrNibble=[]
# for indxOfBit in range(0,4):
# lstBitReprOfCurrNibble.append(intNibbleValue>>indx OfBit&0x01)
# #:for
# lstBitReprOfCurrNibble.reverse()
#
dctLstOfBitsVsCharOfNibble['%X'%(intNibbleValue,)]=lstBitReprOfCurrNibble
# #:for

dctLstOfBitsVsOrdOfChar = {}
for ordOfChar in range(256):
dctLstOfBitsVsOrdOfChar[ordOfChar] =
dctLstOfBitsVsCharOfNibble['%X'%(ordOfChar>>4,)] +
dctLstOfBitsVsCharOfNibble['%X'%(ordOfChar&0x0F,)]
#:for
# what gives: {
# 0x00:[0, 0, 0, 0, 0, 0, 0, 0],
# 0x01:[0, 0, 0, 0, 0, 0, 0, 1],
# 0x02:[0, 0, 0, 0, 0, 0, 1, 0],
# ...
# 0xFD:[1, 1, 1, 1, 1, 1, 0, 1],
# 0xFE:[1, 1, 1, 1, 1, 1, 1, 0],
# 0xFF:[1, 1, 1, 1, 1, 1, 1, 1]
# }
dctLstOfBitsVsHexOfChar = {}
for ordOfChar in range(256):
dctLstOfBitsVsHexOfChar['%02X'%ordOfChar] =
dctLstOfBitsVsOrdOfChar[ordOfChar]
#:for
# what gives: {
# '00':[0, 0, 0, 0, 0, 0, 0, 0],
# '01':[0, 0, 0, 0, 0, 0, 0, 1],
# '02':[0, 0, 0, 0, 0, 0, 1, 0],
# ...
# 'FD':[1, 1, 1, 1, 1, 1, 0, 1],
# 'FE':[1, 1, 1, 1, 1, 1, 1, 0],
# 'FF':[1, 1, 1, 1, 1, 1, 1, 1]
# }

n = 0
NoOf32bitChunks = 0
lstBitsBitwiseAnd = []
lstBitsModulo = []
lstViaBitChunks = []
lstBitsViaHex = []
lstBitsViaMod = []
lstBitsGMPY = []
lstViaHexAndArray = []
lstViaModAndArray = []
timeBitwiseAnd = -1
timeModulo = -1
timeBitsViaHex = -1
timeBitsViaMod = -1
timeViaBitChunks = -1
timeGMPY = -1
timeViaHexAndArray = -1
timeViaModAndArray = -1

bitChunkSize = 30 # must be <= 32

while timeBitwiseAnd <= timeBitsViaHex + 0.001:

n = (n<<32) + 0x12345678

NoOf32bitChunks += 1

i = n
lstBitsModulo = []
start = time.clock()
while i:
lstBitsModulo.append(i%2)
i=i>>1
timeModulo = time.clock()-start

i = n
lstBitsBitwiseAnd = []
start = time.clock()
while i:
lstBitsBitwiseAnd.append(i&0x01)
i=i>>1
timeBitwiseAnd = time.clock()-start

i = n
lstViaBitChunks = []
bitFilter = 0
for dummy in range(bitChunkSize):
bitFilter = (bitFilter<<1)+1
#:for

start = time.clock()
done = False
while i:
i1 = int(i & bitFilter) # int() converts here a long-integer to integer
i >>= bitChunkSize
if i == 0: done = True
for k in xrange(bitChunkSize):
lstViaBitChunks.append(i1 & 1)
i1 >>= 1
if done and i1==0:
# if this is the top word, and no bits are left, we are done
break
#:if
#:for
#:while
timeViaBitChunks = time.clock()-start

i = n
# lstBitsViaHex = []
start = time.clock()
strHexOf_i = i.__hex__()[2:]
if strHexOf_i[-1]=='L':
strHexOf_i=strHexOf_i[0:-1]
#:if
intNoOfLeadingZeroBits = 0
lstBitsOfFirstNibble = dctLstOfBitsVsCharOfNibble[strHexOf_i[0]]
while not lstBitsOfFirstNibble[intNoOfLeadingZeroBits] and
intNoOfLeadingZeroBits < 4:
intNoOfLeadingZeroBits += 1
#:while
if intNoOfLeadingZeroBits == 4:
lstBitsViaHex = []
else:
lstBitsViaHex = lstBitsOfFirstNibble[intNoOfLeadingZeroBits:]
#:if
for indxToStrHexOf_i in range(1,len(strHexOf_i)):
lstBitsViaHex +=
dctLstOfBitsVsCharOfNibble[strHexOf_i[indxToStrHexOf_i]]
#:for
lstBitsViaHex.reverse()
timeBitsViaHex = time.clock()-start

i = n
# lstBitsViaMod = []
start = time.clock()
strHexOf_i = '%X'.__mod__(i)
intNoOfLeadingZeroBits = 0
lstBitsOfFirstByte = dctLstOfBitsVsHexOfChar[strHexOf_i[0:2]]
while not lstBitsOfFirstByte[intNoOfLeadingZeroBits] and
intNoOfLeadingZeroBits < 8:
intNoOfLeadingZeroBits += 1
#:while
if intNoOfLeadingZeroBits == 8:
lstBitsViaMod = []
else:
lstBitsViaMod = lstBitsOfFirstByte[intNoOfLeadingZeroBits:]
#:if
for indxToStrHexOf_i in range(2,len(strHexOf_i),2):
lstBitsViaMod +=
dctLstOfBitsVsHexOfChar[strHexOf_i[indxToStrHexOf_i:indxToStrHexOf_i+2]]
#:for
lstBitsViaMod.reverse()
timeBitsViaMod = time.clock()-start

i = n
lstViaHexAndArray = []
import array, binascii
start = time.clock()
strHexOf_i = i.__hex__()[2:]
if strHexOf_i[-1]=='L':
strHexOf_i=strHexOf_i[0:-1]
#:if
for item in array.array('B', binascii.unhexlify(strHexOf_i)):
lstViaHexAndArray += dctLstOfBitsVsOrdOfChar[item]
#:for
intNoOfLeadingZeroBits = 0
while not lstViaHexAndArray[intNoOfLeadingZeroBits] and
intNoOfLeadingZeroBits < 4:
intNoOfLeadingZeroBits += 1
#:while
if intNoOfLeadingZeroBits == 4:
lstViaHexAndArray = []
else:
lstViaHexAndArray = lstViaHexAndArray[intNoOfLeadingZeroBits:]
#:if
lstViaHexAndArray.reverse()
timeViaHexAndArray = time.clock()-start

i = n
lstViaModAndArray = []
import array, binascii
start = time.clock()
strHexOf_i = '%X'.__mod__(i)
for item in array.array('B', binascii.unhexlify(strHexOf_i)):
lstViaModAndArray += dctLstOfBitsVsOrdOfChar[item]
#:for
intNoOfLeadingZeroBits = 0
while not lstViaModAndArray[intNoOfLeadingZeroBits] and
intNoOfLeadingZeroBits < 4:
intNoOfLeadingZeroBits += 1
#:while
if intNoOfLeadingZeroBits == 4:
lstViaModAndArray = []
else:
lstViaModAndArray = lstViaModAndArray[intNoOfLeadingZeroBits:]
#:if
lstViaModAndArray.reverse()
timeViaModAndArray = time.clock()-start

import gmpy
lstBitsGMPY = []
# start = time.clock()
# i = gmpy.mpz(n)
# f = gmpy.scan1(i,0)
# if f==0:
# lstBitsGMPY.append(1)
# k = 1
# f = gmpy.scan1(i,1)
# else:
# k = 0
# while f:
# while k<f:
# lstBitsGMPY.append(0)
# k += 1
# lstBitsGMPY.append(1)
# k += 1
# f = gmpy.scan1(i,f+1)
# timeGMPY = time.clock()-start
# gmpy.binary(i) delivers base-256 little endian binary
representation i.e. :
# gmpy.binary(0x12131415) == '\x15\x14\x13\x12'
# so it can't be directly used here in the given context.
start = time.clock()
i = gmpy.mpz(n)
strBitsOf_i = gmpy.digits(i,2)
for char in strBitsOf_i:
if char=='0':
lstBitsGMPY.append(0)
else:
lstBitsGMPY.append(1)
#:for
lstBitsGMPY.reverse()
timeGMPY = time.clock()-start

#:while

if( lstBitsBitwiseAnd == lstBitsModulo
and lstBitsBitwiseAnd == lstBitsViaHex
and lstBitsBitwiseAnd == lstBitsViaMod
and lstBitsBitwiseAnd == lstBitsViaHex
and lstBitsBitwiseAnd == lstViaBitChunks
and lstBitsBitwiseAnd == lstViaHexAndArray
and lstBitsBitwiseAnd == lstViaModAndArray
and lstBitsBitwiseAnd == lstBitsGMPY ):
print
print ' Seconds for bit extraction from integer with %i hex-digits
when: '%(NoOf32bitChunks*8,)
print
print ' looping over i>>1;i&0x01 = %f '%(timeBitwiseAnd,)
print ' ^-- but in %i bit chunks = %f '%(bitChunkSize,
timeViaBitChunks)
print ' looping over i>>1;i%%2 = %f '%(timeModulo,)
print ' using i.__hex__() repr. = %f '%(timeBitsViaHex,)
print ' using \'%%02X\'.__mod__(i) = %f '%(timeBitsViaMod,)
print ' using __hex__,array,binascii = %f '%(timeViaHexAndArray,)
print ' using __mod__,array,binascii = %f '%(timeViaModAndArray,)
print ' using gmpy.digits(i,2) = %f '%(timeGMPY,)
print
print ' Bits extraction from long integers with number of
hexadecimal digits '
print ' > %i '%(NoOf32bitChunks*8,)
print ' is at least 1 ms faster with i.__hex__() then with
i>>1;i&0x01 method.'
print
print ' Modulo division (%2) is always slower than bitwise-and (&0x01).'