{"id":5224,"date":"2023-08-29T16:14:18","date_gmt":"2023-08-30T00:14:18","guid":{"rendered":"https:\/\/wonghoi.humgar.com\/blog\/?p=5224"},"modified":"2024-02-13T01:59:21","modified_gmt":"2024-02-13T09:59:21","slug":"programming-techniques-bit-hackery","status":"publish","type":"post","link":"https:\/\/wonghoi.humgar.com\/blog\/2023\/08\/29\/programming-techniques-bit-hackery\/","title":{"rendered":"Programming Techniques: Bit hackery"},"content":{"rendered":"\n

Sean Eron Anderson (Stanford CS graphics lab)’s bit twiddling pages often shows a bunch of neat bit tricks, but it’s more like a recipe book than a unified way to summarize the common concepts behind them. Here’s my attempt. This page will get updated as I got the time and more useful insights collected.<\/p>\n\n\n\n

Concept: Two ways to get two’s complement<\/h2>\n\n\n\n

This is the basics of most bit hacks below. Sometimes the definition itself is a bit trick on its own.<\/p>\n\n\n\n

\\begin{align}\n\\overline{-x}+1=x \\\\\n-x = \\overline{x}+1 \n\\end{align}<\/pre><\/div>\n\n\n\n
the above reads: to flip sign, flip bits then add one.<\/p>\n\n\n\n
\\begin{align}\n\\overline{x} = -x-1 \\\\\n\\end{align}<\/pre><\/div>\n\n\n\n
the above reads: if you flip the bits, you are getting the negative of it subtracted by 1. e.g. ~4 = -5, ~5 = -6, …, ~(-5) = 4, ~(-4) = 3, …<\/p>\n\n\n\n
\\begin{align}\nx = \\overline{-x-1} \\\\\n\\end{align}<\/pre><\/div>\n\n\n\n
the above reads: any number can be represented by its negative minus -1, then bit-flipped.<\/p>\n\n\n\n
\\begin{align}\n\\overline{-x} = x-1 \\\\\n-x = \\overline{x-1}\n\\end{align}<\/pre><\/div>\n\n\n\n
reads: to flip sign, subtract one first then flip bits <\/p>\n\n\n\n
So it means to change signs, you can choose to subtract<\/strong> one first then flip bits or flip bits first then add<\/strong> one. <\/p>\n\n\n\n
-x=\\overline{x-1} = \\overline{x}+1 <\/pre><\/div>\n\n\n\n
Let’s try it with 2 instead of 1:<\/p>\n\n\n\n
\\overline{x-2} = \\overline{(x-1)-1} = \\overline{x-1}+1 = (\\overline{x}+1)+1 = \\overline{x}+2<\/pre><\/div>\n\n\n\n
You can generalize it to an arbitrary number by subtracting -1 more under the bar on the left hand side and you will get +1 more on the right hand side. Every extra -1 under the bar (bit flips) shows up as +1 outside the bar (bit flips).<\/p>\n\n\n\n
\\overline{x-3} = \\overline{(x-2)-1} = \\overline{x-2}+1 = (\\overline{x}+2)+1 = \\overline{x}+3<\/pre><\/div>\n\n\n\n
This matches the observation that complement schemes (one’s or two’s) both have increasing magnitude move in opposite directions for positive and negative numbers. Look at this table: <\/p>\n\n\n\n
Unsigned<\/td>Binary<\/td>Two’s Complement<\/td><\/tr>
7<\/td>111<\/td>-1<\/td><\/tr>
6<\/td>110<\/td>-2<\/td><\/tr>
5<\/td>101<\/td>-3<\/td><\/tr>
4<\/td>100<\/td>-4<\/td><\/tr>
3<\/td>011<\/td>3<\/td><\/tr>
2<\/td>010<\/td>2<\/td><\/tr>
1<\/td>001<\/td>1<\/td><\/tr>
0<\/td>000<\/td>0<\/td><\/tr><\/tbody><\/table>
A very important observation that’d be used over and over blow is that in two’s complement,  -1 is always a mask of all binary ‘1’s regardless of the word width.<\/figcaption><\/figure>\n\n\n\n
This rule can also read as: magnitude offsets goes in opposite directions <\/p>\n\n\n\n
\\begin{align}\n-x+(n-1)=\\overline{x-n} = \\overline{x}+n\n\\end{align}<\/pre><\/div>\n\n\n\n
Note that this is NOT distributing<\/span> bit-flip<\/strong> to two addition\/subtraction despite it resembles it with an important distinction that the sign of n<\/code> changed without turning into (n-1). If it were to distribute, you’ll get (n-2) on the left-hand-side instead of the (n-1) term because the -1 would have been counted twice under distribution. <\/p>\n\n\n\n
Bit flips simply doesn’t distribute over the 4 basic (algebraic field) operations. The two’s complement offset is done once and only once<\/em> when you change the overall representation no matter how many components you break it down into. It’s merely done to shift over the -0<\/code> in one’s complement so there’s an extra space for an extra negative number \"-2^n$\" which its positive counterpart \"+2^n$\" is not representable without starting a new digit.<\/p>\n\n\n\n
Note to self: the INT_MIN is just the sign bit of ‘1’ followed by all zeros after.<\/p>\n\n\n\n
Concept: XOR can be used for bit flips or check for bit changes<\/h2>\n\n\n\n
Concept: Top bit holds the sign<\/h2>\n\n\n\n
Sounds simple, but if you keep in mind that (x<0)<\/code> is really asking to see if the top bit is 1, you can check if two numbers has opposite signs without bit shifting it down by simply XOR-ing them (anything below the top bit are ignored) and use (x^y)<0<\/code> to check for the resulting top bit is 1, which signals that the sign bits are different.<\/p>\n\n\n\n
Concept: Sign extensions (the top\/sign bit gets drag-copied when right shifted)<\/h2>\n\n\n\n
When you right shift (in signed integers), the top (sign) bit gets drag-copied (sign extended) by the number of bits you right shifted. (Obviously for signed integers, right shifts are zero-filled)<\/p>\n\n\n\n
Can exploit this to<\/p>\n\n\n\n
    \n
  • drag the top (sign) bit all the way down to the bottom (so you either get all 1s or 0s) to provide a conditional mask based on the sign (see below)<\/li>\n<\/ul>\n\n\n\n
    1??????? \\gg 7 \\textnormal{ (i.e. type bit width - 1)} = 11111111_2 = -1_{10} \\\\\n0??????? \\gg 7 \\textnormal{ (i.e. type bit width - 1)} = 00000000_2 = +0_{10} \\\\<\/pre><\/div>\n\n\n\n
    Signed extensions also means a negative number will stay negative and a positive number will stay positive if you right shift<\/p>\n\n\n\n
    Sign extension behavior is not guaranteed by 1987 ANSI C, but it’s standard on pretty much anything more modern than that. Just make sure anything that uses this behavior are inlined (so the implementation can be easily swapped out), well documented\/commented, and platform checks\/switches are in place, and there’s a way to quickly check with the slower but platform independent implementation. <\/p>\n\n\n\n
    Concept: Getting a bit mask of a 1s (if true) and all 0s (if false)<\/h2>\n\n\n\n
    The ability to convert a logic evaluation (condition) that gives <\/p>\n\n\n\n
    \\begin{align*}\n00000001_2 &= +1_{10} & \\mathrm{(true)}\\\\\n00000000_2 &= +0_{10} & \\mathrm{(false)}\n\\end{align*}<\/pre><\/div>\n\n\n\n
    into a conditional <\/strong>mask that gives<\/p>\n\n\n\n
    \\begin{align*}\n11111111_2 &= -1_{10} & \\mathrm{(true)}\\\\\n00000000_2 &= +0_{10} & \\mathrm{(false)}\n\\end{align*}<\/pre><\/div>\n\n\n\n
    is the basis of many branchless ‘drop\/keep this if that’ operations.<\/p>\n\n\n\n
    This can also be achieved by <\/p>\n\n\n\n