Posts with tag: low-level
Bit tricks - Counting the number of 1 bits (Kernighan algorithm)
Sat Oct 22 2022It's been too long since the last bit tricks article, so I thought I would share another one! This time we will look at a simple fun bit trick to count the number of 1 bits in a binary string (e.g, a 32 bit integer). This algorithm was discovered by Brian Kernighan of Bell Labs and C fame. Unlike the previous algorithm presented in my bit tricks series, this one requires some branching.
Read more..Bit tricks - Absolute value without branching
Mon Feb 14 2022Bit trickery is always interesting! Sometimes you can use them to avoid branching (like if-checks), other times they are useful to save a few CPU cycles to avoid expensive operations. The absolute value trick I will show you here, is mostly to avoid branching. Why would you want to avoid branching? Many newer processors, from the mid 90s and onward, do something called pipelining to achieve a form of instruction level parallelism. While a classic processor fetch an instruction, decode it, then execute, a pipelined processor can fetch the next instruction while the previous one is decoded. You can have multiple operations like this almost in parallel. If we have to branch, like for an if-check, we might not have fetched the correct next instruction anymore, and might have to fetch new ones (for the whole pipeline). This can be an expensive operation. Calculating absolute values is a problem where we often have to have a branch (an if-check for smaller than 0).
Read more..
