Jump to content


Photo

Hamming weight


  • This topic is locked This topic is locked
1 reply to this topic

#1 Hyomoto

Hyomoto

    GMC Member

  • GMC Member
  • 276 posts
  • Version:GM:Studio

Posted 08 January 2016 - 10:21 PM

I was trying to use this converted over from Bit Twiddling Hacks but it seems to fail when the first two bits are set.  Clearly I've dunced something up but as far as my limited bit skills can take me I'm not sure what it is.  It's supposed to count the number of bits in a 32 bit integer, which I assume could be the culprit, but I find it odd its only the first two bits that mess it up.  They add 257 to the returned value or 514 if they are both set.  The rest of the bits are counted fine.

Any master builders want to take a swing?

/// int popcnt(value)
//   any :: function; returns the number of bits set in value
var v = argument0, c;

v = v - ((v >> 1) & $55555555);
v = (v & $33333333) + ((v >> 2) & $33333333);
c = ((v + (v >> 4) & $F0F0F0F) * $1010101) >> 24;

return c;

EDIT:  I realized I'm an idiot, it isn't the first two values, it's 256 and 512.  I assume this problem will be witnessed for bits beyond those numbers as well though I haven't tested anything higher.  It properly counts the bits set in any number 255 or lower, must diagram the problem ...

 

So basically, as each bit rises, ie: (1 << x++), it returns 1 until bit 9 at which point it returns 257.  Adding in a lower bit gives 258.  Adding in a higher bit gives 514.  So, 257 x 2.  I'm guessing it's either a flaw in using this operation on a double, which while I don't fully understand the wizardry at work seems like it should be fine as long as your integer doesn't exceed 32 bits, or and OOO mistake or something like that.

 

EDIT 2: Well, it seems I was able to implement HAKMEM 169 and it does indeed work, at least for my purposes.

/// int popcnt(value)
//   any :: function; returns the number of bits set in value
var v = argument0, c;

c = v - ((v >> 1) & $DB6DB6DB)
      - ((v >> 2) & $49249249);
      
return (c + (c >> 3) & $C71C71C7) % 63;

So yeah, if you need a hamming weight for a 32-bit number, there you go.


Edited by Hyomoto, 09 January 2016 - 12:04 AM.

  • 0

#2 hercludes

hercludes

    std::Octothorpe

  • GMC Member
  • 207 posts
  • Version:None

Posted 13 February 2016 - 08:37 AM

It does not work.

 

0xFFFFFFFF gives me 33,

0xFFFFFFFE  and 0XFFFFFFFD gives me 32,

0xFFFFFFFC gives me 31,

FFFFFFF0 = 29, etc

 

Too tired to look into where you're getting problems. I see you based yours off HAKMEM169. I think it is impossible to do the HAKMEM169 version without using 64-bit version, at least all the code snippets I've seen relied on numbers such as 0x033333333333. There are some easy-to-understand variations of the HAKMEM 169 algorithm somewhere on the internet.  Anyways, I always liked Brian Kernighan's method:

while ((v &= v - 1, ++ c, v));

It only goes through as many iterations as there are set bits. Anyways, the best way you can count set bits is by doing it in parallel, like so:

v = v - ((v >> 1) & $55555555); // count duo-bits
v = (v & $33333333) + ((v >> 2 ) & $33333333); // count nibble bits
return ((v + (v >> 4) & $F0F0F0F) * $1010101) >> 24; // count byte-counts and get sum

The sum total of the bits is calculated by multiplying by 0x1010101 (get the final result in the MSB) and shifting right 24 bits. There's a generalization of this method of any bit width up to like 128 or something, it's a bit out of my league. But this algorithm is more efficient than HAKMEM169 anyways.


Edited by hercludes, 13 February 2016 - 08:44 AM.

  • 0

Most projects use C++ in OpenGL/SDL. I occasionally use As3 or Haxe.
Other languages I know: C, Java, Perl, Python, Ruby, ASM(8086 & M68k), Lua, Brain****
Languages I have dabbled in: Rust, D, Haskell, Clojure, Prolog, SmallTalk

Assembly programming puzzle game based off the 8086 made in ten days for GiTD 50.

DpnrY.jpg