Demystifying bitwise operations, a gentle C tutorial

Post by _a_a_a_ » Sat, Mar 04, 2023, 10:30 AM UTC

chongli wrote: post #62

_a_a_a_ wrote: post #33

Earlier quoted context omitted.

There are quite a lot of bit hacks on the web, but Hackers Delight is where it took off for me.It was a massive eye-opener, what was possible and even better doing it the old-fashioned way. The second book is very, very heavy on division and as such it's not really as much 'fun' as the original, however I'd still recommend it! I shared the original Hackers delight with a work colleague, who had a mathematical bent an…

The second book is very, very heavy on division and as such it's not really as much 'fun' as the original, however I'd still recommend it! What do you mean by this? Did they merely add a ton of information on division? Or did they take out the 'fun' bits from the original and replace them with division stuff?

Post by mtlmtlmtlmtl » Sat, Mar 04, 2023, 12:56 PM UTC

wruza wrote: post #80

The bitwise XOR operator (^) is a binary operator that compares the corresponding bits of two operands and returns a new value where each bit is set to 1 if the corresponding bits of the operand are different, and 0 if they are the same. You may also think about XOR in a following way: Any “1” in B flips (inverts) the corresponding bit in A. It’s like a vectorized NOT operation for single bits. Also works the other w…

  Ob010 + 0b011 = 0b101 (carry is propagated to the 3rd bit)
  0b010 ^ 0b011 = 0b001 (same result with no carry)

Post by bluesnowmonkey » Sat, Mar 04, 2023, 2:52 PM UTC

winstonprivacy wrote: post #84

This is great. However, he omitted one I encountered a need for pretty recently and have so far not found a good solution: How do you count the number of bits which have been set in a bitfield of type uint32_t? I couldn't find any x64_64 intrinsics for this, which would probably be incredibly efficient.

Post by winstonprivacy » Sat, Mar 04, 2023, 4:01 PM UTC

philiplu wrote: post #86

winstonprivacy wrote: post #84

This is great. However, he omitted one I encountered a need for pretty recently and have so far not found a good solution: How do you count the number of bits which have been set in a bitfield of type uint32_t? I couldn't find any x64_64 intrinsics for this, which would probably be incredibly efficient.

Like bluesnowmonkey says, the concept you're looking for is called popcount, for population count. It's also called the Hamming weight. Wikipedia has 5 different example implementations under that latter name. Many C/C++ compilers have it available as an intrinsic as well, like __builtin_popcount or __popcnt. It's also std::popcount in C++20.

  // 19 instructions, does not use intrinsics
  int countbits(unsigned x) {
    unsigned n;
    n = (x >> 1) & 0x77777777;
    x = x - n;
    n = (n >> 1) & 0x77777777;
    x = x - n;
    n = (n >> 1) & 0x77777777;
    x = x - n;
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x\*0x01010101;
    return x >> 24;
  }

Post by lolcatuser » Sat, Mar 04, 2023, 6:19 PM UTC

ziml77 wrote: post #70

layer8 wrote: post #46

Earlier quoted context omitted.

This is one case where lining up values (and surrounding operators with spaces) can be good practice: tx_data[43] = utime >> 24; tx_data[44] = utime >> 16; tx_data[45] = utime >> 8; tx_data[46] = utime >> 0; Or even: tx_data[43] = utime >> (3 * 8); tx_data[44] = utime >> (2 * 8); tx_data[45] = utime >> (1 * 8); tx_data[46] = utime >> (0 * 8);

I've done the >> 0 thing to make it very clear what's going on, but I hadn't considered the * 8 construction. That's actually easier to comprehend at a glance because the numbers become less "magic". (8 and 16 are obvious to me, but 24 always has me second-guessing myself somewhere in the back of my mind)

  x 

  x