Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Demystifying bitwise operations, a gentle C tutorial

andreinc.net

Post reply on HN
Print view View original

71–80 of 95 posts

Re: Demystifying bitwise operations, a gentle C tutorial

#71

Post by nomemory »

tapatio wrote: post #64

The graphics are impressive. Specifically, I've never seen someone fold a "bit surface" in half like that. I've also never seen a ladder view. Assuming Andrei Ciobanu himself posted this, how did you come up with those views? Bored on a Friday night?

I am not sure if this is all that original, I am sure what other have seen that before. For me it clicked when I was redoing the graphics.

What it's more interesting is that symmetry is specific to numbers in general, and the way we represent them. As an exercise if you use base 3, and plot more numbers you will also see hidden patterns.

Thanks for noticing that section.

Re: Demystifying bitwise operations, a gentle C tutorial

#72

Post by GuB-42 »

cactusplant7374 wrote: post #10

I don’t understand why bit masking and manipulation is so popular when it makes the code impossible to read. I like using Ruby, string, and pack and unpack.

It takes some getting used to but the operations by themselves are readable, it is just that what you do with them can be complex. It is like arithmetic. People usually don't have a problem with addition, subtraction, multiplication and division, but it doesn't mean they won't have a hard time dealing with complex equations.

Packing and unpacking are just some of the things you can do with bitwise operations. They are a common problem, and they are often tricky, so having an API for that makes a lot of sense. But if what you need to do is not packing and unpacking, I find it harder to understand the unpack -> string manipulation -> pack workflow than bitwise operations, it also tends to be more verbose and slower.

Re: Demystifying bitwise operations, a gentle C tutorial

#73

Post by 3pm »

Great article. One potential improvement is not to call Two's complement MSB a 'sign bit'. It implies that it only stores a sign which is how 'Signed magnitude' works. With all its downsides like having two representations for 0 etc. The beauty of Two's complement is that everything works exactly like unsigned representation, with the exception of MSB. In Two's complement MSB contributes either 0 or negative 2^N-1. So for 8 bit signed numbers, most significant bit contributes either 0 or -128. Everything else, subtraction, hardware adders etc work the same. Signed numbers are basically numbers with a flexible number line, and the first bit represents where this number line starts. I personally remember MSB for signed integers as 'origin bit'.

Re: Demystifying bitwise operations, a gentle C tutorial

#74

Post by dchapp »

I see several people sharing the Stanford bithacks link, so I'll throw in a slightly-less well-known resource that I found particularly instructive. Basically, a collection of the lemmata we can prove about fixed-length sequences of bits and the fun algorithms that can be built atop those results.

https://www.jjj.de/fxt/

And for the non-pdf-phobic: https://www.jjj.de/fxt/fxtbook.pdf

Re: Demystifying bitwise operations, a gentle C tutorial

#75

Post by olliej »

I just do not understand why this document is so large - there just is not enough complexity in bitwise operators to warrant this giant multi chapter document. If anything I feel it will be confusing because it’s so much text being used to describe so little actual logic.

Re: Demystifying bitwise operations, a gentle C tutorial

#76

Post by whateveracct »

plugin-baby wrote: post #52
whateveracct wrote: post #35

Earlier quoted context omitted.

I think if you work with UUIDs, it's worth learning about bitwise stuff. So backend developers in general. It's not a day-to-day skill, but it is one I've used at just about every job in the last decade to elegantly and efficiently solve hard problems regarding idempotency and randomness.

When would you want to perform bitwise operations on a UUID?

Say you need 5 UUIDs derived from one (say a primary key and some set of idempotency keys). You can mask them.

Re: Demystifying bitwise operations, a gentle C tutorial

#77

Post by gdprrrr »

wg0 wrote: post #39

I'm trying to find some good resources or some book that covers modern C. For everything else from Python to Golangz Rust and everything in between - there are tons of quality books and even their own documentation in some cases is pretty decent. But not so with C. If you read this and have something, please share. Just C (not much interested in C++)

https://www.youtube.com/watch?v=QpAhX-gsHMs

Re: Demystifying bitwise operations, a gentle C tutorial

#78

Post by hahamaster »

I totally intuitively understand bitwise operators in C because I grew up with assembler and all this was my second nature.

I’m afraid this article is unnecessarily complicated. The things that are eventually illuminated are really trivially simple, it’s just that they are explained in a complicated way.

Re: Demystifying bitwise operations, a gentle C tutorial

#79

Post by flyingcircus3 »

amenghra wrote: post #16

A related puzzle: https://www.quaxio.com/know_your_bits/ More such puzzles: http://www.cs.cmu.edu/afs/cs/academic/class/15213-f02/www/L1... and http://csapp.cs.cmu.edu/public/datalab.pdf Bit Twiddling Hacks: http://graphics.stanford.edu/~seander/bithacks.html

For the first puzzle, code that determines if a value has one bit high, without any if/while/for, here's what I got:

!(x & (x-1)) && x

Was there a "best" solution somewhere? I couldnt get the code window to work.

Re: Demystifying bitwise operations, a gentle C tutorial

#80

Post by wruza »

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 way (xor is commutative, A^B === B^A). This way of thinking is helpful when you see expressions like:

  X ^ (1
Which means “X with bit 3 flipped”. (3 means 4th from the right, as in …3210).
Post reply on HN