3 ms·

Man, I wish languages gave us easy access to these sorts of instructions. So many times I've written a loop to count how many times divisible by 2 a number is,

Man, I wish languages gave us easy access to these sorts of instructions. So many times I've written a loop to count how many times divisible by 2 a number is, when there has to be an instruction for that... yes, notionally I could drop down into assembly, but that would require learning how to do so in the relevant language! Out of curiosity, what is this weird way of computing popcount you mention? I haven't seen it before.

dragontamer 5y ago
> Out of curiosity, what is this weird way of computing popcount you mention? I haven't seen it before. So lets just do 8-bits at a time, in binary. It makes it clear what's going on. Your 8-bit number is: x = x0 x1 x2 x3 x4 x5 x6 x7 * 0x55 is 01010101 in binary. * 0xAA is 10101010 in binary. * (x & 0x55) is (0 & x0) (1 & x1) (0 & x2) (1 & x3)... * (x & 0xaa) is (1 & x0) (0 & x1) (1 & x2) ... * (x & 0x55) + ((x & 0xaa) >> 1) is: |x0 + x1|,|x2 + x3|,|x4+x5|, |x6+x7|, where |blahblah| is a 2-bit number taking up 2-bits of the 8-bit number. * step2 = (x & 0x55) + ((x & 0xaa) >> 1) * (step2 & 0x33) is now |00| |x2+x3| |00| |x6+x7| * (step2 & 0xcc) is now |x0+x1| |00| |x4+x5| |00| * (step2 & 0x33) + ((step2 & 0xcc) >> 2) is //x0+x1+x2+x3// //x4+x5+x6+x7//, where //blah// is a 4-bit number. You probably can figure out the last step at this point. Take the bottom 4 bits and add them with the top 4 bits. A 2-bit number (such as |x0+x1|) can only take on 3 values: 0, 1, or 2. As such, |x0+x1| will never "carry" outside of the 2-bit space you've allocated for it. Similarly, a 4-bit number (such as //x0+x1+x2+x3//) can only take on 5 values: 0, 1, 2, 3, 4. The 4-bits you've allocated can take on values all the way up to 16, so you also never have to worry about overflow.
- a1369209993 5y ago
  Deliberately more obviously 'weird' version, from memory: uint64_t x = ...; for(size_t i = 1; i<UINT_BIT ;i*=2) // loop unroll { unsigned m = UINT_MAX / ((1<<i)+1); // constant-fold // divide 2^(2k)-1 by 2^k+1 to get 2^k-1 in each group // 2k-bit group means 2^k-1 sets bottom half x = (x & m) + (x>>i & m); // we can save a AND w/o carry but 1-bit and 2-bit // need 2 ANDs to prevent carry between groups // x = (x + (x>>i)) & m; }
deleted 5y ago
[deleted]
jcranmer 5y ago
Rust has methods for these. Most C/C++ compilers have some variation on __builtin_cttz or the like. C++20 adds templated methods rather than builtins in the <bit> header. Java has Integer.bitCount, Integer.numberOfLeadingZeros, etc. since Java 5. I haven't looked at Go, Swift, D, Zig, Nim, etc., but I suspect that all of them will have some variation on this theme.
nwmcsween 5y ago
Because ideally you want a language that can express the intent without hard coding for a specific arch

dragontamer 5y ago

> Out of curiosity, what is this weird way of computing popcount you mention? I haven't seen it before. So lets just do 8-bits at a time, in binary. It makes it clear what's going on. Your 8-bit number is: x = x0 x1 x2 x3 x4 x5 x6 x7 * 0x55 is 01010101 in binary. * 0xAA is 10101010 in binary. * (x & 0x55) is (0 & x0) (1 & x1) (0 & x2) (1 & x3)... * (x & 0xaa) is (1 & x0) (0 & x1) (1 & x2) ... * (x & 0x55) + ((x & 0xaa) >> 1) is: |x0 + x1|,|x2 + x3|,|x4+x5|, |x6+x7|, where |blahblah| is a 2-bit number taking up 2-bits of the 8-bit number. * step2 = (x & 0x55) + ((x & 0xaa) >> 1) * (step2 & 0x33) is now |00| |x2+x3| |00| |x6+x7| * (step2 & 0xcc) is now |x0+x1| |00| |x4+x5| |00| * (step2 & 0x33) + ((step2 & 0xcc) >> 2) is //x0+x1+x2+x3// //x4+x5+x6+x7//, where //blah// is a 4-bit number. You probably can figure out the last step at this point. Take the bottom 4 bits and add them with the top 4 bits. A 2-bit number (such as |x0+x1|) can only take on 3 values: 0, 1, or 2. As such, |x0+x1| will never "carry" outside of the 2-bit space you've allocated for it. Similarly, a 4-bit number (such as //x0+x1+x2+x3//) can only take on 5 values: 0, 1, 2, 3, 4. The 4-bits you've allocated can take on values all the way up to 16, so you also never have to worry about overflow.

a1369209993 5y ago
Deliberately more obviously 'weird' version, from memory: uint64_t x = ...; for(size_t i = 1; i<UINT_BIT ;i*=2) // loop unroll { unsigned m = UINT_MAX / ((1<<i)+1); // constant-fold // divide 2^(2k)-1 by 2^k+1 to get 2^k-1 in each group // 2k-bit group means 2^k-1 sets bottom half x = (x & m) + (x>>i & m); // we can save a AND w/o carry but 1-bit and 2-bit // need 2 ANDs to prevent carry between groups // x = (x + (x>>i)) & m; }

deleted 5y ago

[deleted]

jcranmer 5y ago

Rust has methods for these. Most C/C++ compilers have some variation on __builtin_cttz or the like. C++20 adds templated methods rather than builtins in the <bit> header. Java has Integer.bitCount, Integer.numberOfLeadingZeros, etc. since Java 5. I haven't looked at Go, Swift, D, Zig, Nim, etc., but I suspect that all of them will have some variation on this theme.

nwmcsween 5y ago

Because ideally you want a language that can express the intent without hard coding for a specific arch