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

41–50 of 95 posts

Re: Demystifying bitwise operations, a gentle C tutorial

#41

Post by zh3 »

zoomablemind wrote: post #38
zh3 wrote: post #32

Funnily enough just spent a day tracking down a weird problem in an embedded system - some event timestamps were getting corrupted in a weird way. The pattern wasn't obvious until in desperation I dumped them in hex and found the second MSB was toggling between 0 and 1 (whereas it should have been been part of a count sequence). That told me exactly where to look - where the count was re-assembled from four bytes and…

tx_data[44] = utime>16; Good catch! I wonder if this would have been flagged with -Wall?

Nope, code was clean with -Wall on arm-9 compiler (i.e. gcc).

Interesting thought now you say that (no warning) - only found it because of seeing the pattern (apropos the article) and from that having a good idea what was causing it (knowing the int was assembled a byte at a time).

If I had a criticism of modern compilers, it's the blizzard of uninteresting warnings ("strncmp takes const char star, did you really mean to pass it unsigned char star") that make people want to not use -Wall.

Re: Demystifying bitwise operations, a gentle C tutorial

#42

Post by mras0 »

whb07 wrote: post #18

I’ve found significant code in c/c++ where bitwise operations are done for things like division etc by shifting a certain way. I Can imagine in the past, this was “faster”, yet clang/gcc can emit the same by just writing a basic A/B function. Seems the win goes to readability by reducing some of these old school hacks. What say you, greybeards ?

One thing to consider is that the compiler can't simply replace a division by just a right shift for signed variables (it will round towards -inf for negative numbers), so even today there's a tiny bit of benefit of explicitly using shifts if you know that the number can't be negative (and the compiler can't prove it) or you don't care about the rounding (https://godbolt.org/z/vTzYYxqz9).

Of course that tiny bit of extra work is usually negligible, but might explain why the idiom has stuck around longer than you might otherwise expect.

Re: Demystifying bitwise operations, a gentle C tutorial

#43

Post by unwind »

dhosek wrote: post #26
whb07 wrote: post #18

I’ve found significant code in c/c++ where bitwise operations are done for things like division etc by shifting a certain way. I Can imagine in the past, this was “faster”, yet clang/gcc can emit the same by just writing a basic A/B function. Seems the win goes to readability by reducing some of these old school hacks. What say you, greybeards ?

Oh definitely. Some of this goes back to my 6502 assembly days when there was no hardware multiply instruction. So to multiply by 40, for example. I would shift right 3 bits, store the result, shift right 2 more bits and add the stored result. Similarly, a fast divisibility test (we’ll assume we’re dividing n by some odd prime p ): 1. Shift the bits of p right so that there is a 1 in the last position. 2. If n = p th…

Left, you would (obviously, this is a typo) shift left. And 3 followed by 2 since 1<<3 is 8, and 1<<5 is 32 and 8+32 is 40.

Re: Demystifying bitwise operations, a gentle C tutorial

#44

Post by layer8 »

Bitwise NOT (~) gives you a bijection between negative and nonnegative integers in two’s complement representation (which negation doesn’t).

This is for example exploited by the return value of Java’s binarySearch() function, which returns the (nonnegative) index of the search key when found, or else the (negative) bitwise NOT of the index where the key would have to be inserted [0]. In other words, it combines a nonnegative int value plus a flag into one int, while making the flag easily testable ([0] As opposed to C’s bsearch(), which only returns a position when the key was found.

Re: Demystifying bitwise operations, a gentle C tutorial

#45

Post by nwallin »

mannyv wrote: post #8

I thought this was going to be ridiculous but it's actually a really good. It's clear enough that you could extend it down to showing how logic gates work. The only thing missing is a little endian discussion; it assumes big endian (network byte order), and that may be confusing for all those x86 users out there.

Endianness isn't relevant to any of the stuff discussed in the article. It is equally applicable to both big endian and little endian architectures.

Re: Demystifying bitwise operations, a gentle C tutorial

#46

Post by layer8 »

zh3 wrote: post #32

Funnily enough just spent a day tracking down a weird problem in an embedded system - some event timestamps were getting corrupted in a weird way. The pattern wasn't obvious until in desperation I dumped them in hex and found the second MSB was toggling between 0 and 1 (whereas it should have been been part of a count sequence). That told me exactly where to look - where the count was re-assembled from four bytes and…

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);

Re: Demystifying bitwise operations, a gentle C tutorial

#47

Post by sumtechguy »

tester756 wrote: post #23
detrites wrote: post #3

While it's based on C, a large chunk of the content is simply a great introduction to number representations in other bases such as binary and hexadecimal etc. Fundamental knowledge and very well explained, and a few insights I've not seen before.

>Fundamental knowledge yes? no? hard to say The number of times I've needed this knowledge during all years of formal education and then years of work would be probably around 3. Then I started working with C and close to hardware and it became something that I need everyday. It's feels like bit proficiency is only useful in some very specific domains. Thought: is HTTP foundational knowledge nowadays? after all whole…

Like you say it really depends on what your job is. For me those bit algo's for a few years were my jam. I was moving data between 4 different CPU types and across 3 different network transports depending on the project and 4 different OS's. You need to know your bits when moving data between diff arch types and across different transport layers. These days most of that same sort of thing I did then? I would drop it into a json text stream and call it a day.

Re: Demystifying bitwise operations, a gentle C tutorial

#48

Post by nomemory »

whb07 wrote: post #18

I’ve found significant code in c/c++ where bitwise operations are done for things like division etc by shifting a certain way. I Can imagine in the past, this was “faster”, yet clang/gcc can emit the same by just writing a basic A/B function. Seems the win goes to readability by reducing some of these old school hacks. What say you, greybeards ?

https://www.andreinc.net/2023/02/01/demystifying-bitwise-ops...

With -O1 it performed the optimisation.

Re: Demystifying bitwise operations, a gentle C tutorial

#49

Post by HarHarVeryFunny »

edflsafoiewq wrote: post #40
zoomablemind wrote: post #38

Earlier quoted context omitted.

tx_data[44] = utime>16; Good catch! I wonder if this would have been flagged with -Wall?

Nope. There's no warning for bool->int conversion: https://stackoverflow.com/questions/28716391/gcc-forbid-impl...

Somewhat oddly even in C++, where bool is a distinct type, g++ doesn't have any warning for implicit bool to int conversion, although clang's clang-tidy "linter" tool does.

Re: Demystifying bitwise operations, a gentle C tutorial

#50

Post by kps »

zoomablemind wrote: post #38
zh3 wrote: post #32

Funnily enough just spent a day tracking down a weird problem in an embedded system - some event timestamps were getting corrupted in a weird way. The pattern wasn't obvious until in desperation I dumped them in hex and found the second MSB was toggling between 0 and 1 (whereas it should have been been part of a count sequence). That told me exactly where to look - where the count was re-assembled from four bytes and…

tx_data[44] = utime>16; Good catch! I wonder if this would have been flagged with -Wall?

clang-tidy has an open issue to catch this. https://github.com/llvm/llvm-project/issues/56009
Post reply on HN