Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #4017

Fast counting of 1-bits of arbitrarily long bit sequences

Show all headers | View raw

Given a n-bit sequence, one may be interested to determine the number
of 1-bits in it. Decades ago, some computers, e.g. those from CDC, had
an instruction delivering the bit count of a computer word, which was
commonly believed to have been specially provided to facilitate some
crypto studies. A fast software bit counting algorithm for n=32 in C is
well-known. In the following is a Python code for arbitrary large
values of n, based on the same idea. Hopefully it could be useful for
some readers.

jdege has converted that to a class, available at:
http://http://s13.zetaboards.com/Crypto/topic/7129099/1/

M. K. Shen

-----------------------------------------------------------------------------------

# Fast counting of 1-bits of variables of n bits (n = 2**logn).
# M. K. Shen, 01.12.2013.

def initbitcount():
   global logn,byten,tpwi,mk
   assert(logn>=4)
   byten=2**logn//8
   tpwi=[2**i for i in range(logn)]
   b55=0x55
   b33=0x33
   b00=0x00
   b0f=0x0f
   bff=0xff
   mk=[]
   mk.append(bm(1,b55,b55))
   mk.append(bm(1,b33,b33))
   mk.append(bm(1,b0f,b0f))
   for i in range(logn-3):
     mk.append(bm(tpwi[i],b00,bff))
   return

def bm(nb,b1,b2):
   global logn,byten,tpwi,mk
   u=0
   for i in range(nb):
     u<<=8
     u|=b1
   for i in range(nb):
     u<<=8
     u|=b2
   c=byten//(2*nb)
   h=2*nb*8
   v=0
   for i in range(c):
     v<<=h
     v|=u
   return(v)

# Delivers number of 1-bits of a n-bit variable x (n=2**logn).
# logn (>= 4) is to be defined and initbitcount() invoked before first
# use of bitcount().

def bitcount(x):
   global logn,byten,tpwi,mk
   for i in range(logn):
     x=(x&mk[i])+((x>>tpwi[i])&mk[i])
   return(x)

# Example:
logn=7
initbitcount()
x=0x4a27a1e3cb477398d804530bce3d9460
print(bitcount(x))

Back to comp.programming | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Fast counting of 1-bits of arbitrarily long bit sequences Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-12-02 19:17 +0100
  Re: Fast counting of 1-bits of arbitrarily long bit sequences Robert Wessel <robertwessel2@yahoo.com> - 2013-12-03 03:44 -0600
    Re: Fast counting of 1-bits of arbitrarily long bit sequences "osmium" <r124c4u102@comcast.net> - 2013-12-03 10:16 -0600
      Re: Fast counting of 1-bits of arbitrarily long bit sequences Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-12-03 21:35 +0000
      Re: Fast counting of 1-bits of arbitrarily long bit sequences Robert Wessel <robertwessel2@yahoo.com> - 2013-12-03 15:47 -0600
    Re: Fast counting of 1-bits of arbitrarily long bit sequences Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-12-03 17:31 +0100
      Re: Fast counting of 1-bits of arbitrarily long bit sequences Robert Wessel <robertwessel2@yahoo.com> - 2013-12-03 15:50 -0600
        Re: Fast counting of 1-bits of arbitrarily long bit sequences Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-12-04 16:03 +0100

csiph-web