Does the POPCNT instruction work on bit vectors of
arbitrary length? e.g. +/b where b has 1e7 bits, say.
A fast method for +/b where b is a bit vector, can be
modelled as follows:
POPCOUNT=: a. {~ +/"1 #: i.256 NB. popcounts for each possible byte
C =: <. 255%8 NB. number of times the maximum popcount for
a byte (viz., 8)
NB. can be added to itself without
overflowing a byte
ic =: 3!:4 NB. for "casting" integers into bytes and
vice versa
popcount=: 3 : 0
assert. 2=3!:0 y
assert. 1=#$y
t=. POPCOUNT{~a.i.y,(4|-#y)$0{a. NB. popcount for each byte
w=. _2 ic t NB. convert to 4-byte integers
m=. ((>.C%~#w),C)$w,C$0 NB. convert into a C-column matrix
z=. +/a.i.2 ic +/"1 m NB. add the byte popcounts 4 at a time, then
total them
assert. z = +/,#: a.i.y
)
popcount 'squeamish ossifrage'
79
popcount 5!:5 <'popcount'
1101
popcount 5{.a.
5
The Roger Moore idea described by Eugene McDonnell in
http://www.jsoftware.com/papers/eem/qq111.htm
is using the translate instruction TR in the IBM S/360
to do what POPCOUNT{~a.i.y does. I am not sure
whether Moore also had the 4-at-a-time idea. Warren's
"Hacker's Delight", section 5.1, http://www.hackersdelight.org
has both ideas.
In C, the converting back and forth between bytes and
words is free. Other than the POPCOUNT table, no
array temp is required.
----- Original Message -----
From: "Robert P. Rumble" <[email protected]>
Date: Monday, September 6, 2010 23:48
Subject: Re: [Jprogramming] Splitting an integer into its digits
To: Programming forum <[email protected]>
> At 08:29 PM 9/6/2010, you wrote:
> >Bytes are directly addressable in the most popular CPUs;
> >bits are not.
> >
> >However, with an additional 20 years of C programming under
> >my belt, I am now confident enough to tackle bit booleans,
> >if I should become interested enough. Bit booleans offer
> >lots of room for lots of juicy tricky clever code. For example,
> >how do you compute +/b where b is a bit-boolean vector?
>
> This may have already been done for you in hardware.
>
> See opcode called popcount or popcnt, aka "the NSA
> instruction" for
> x86 architectures.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
