What is CHAR_BIT?

Quoting the code for computing the integer absolute value (abs) without branching from http://graphics.stanford.edu/~seander/bithacks.html:

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

Patented variation:

r = (v ^ mask) - mask;

What is CHAR_BIT and how use it?

Solution 1:

CHAR_BIT is the number of bits in char. These days, almost all architectures use 8 bits per byte but it is not the case always. Some older machines used to have 7-bit byte.

It can be found in <limits.h>.

Solution 2:

Trying to answer both the explicit question (what is CHAR_BIT) and the implicit question (how does this work) in the original question.

A char in C and C++ represents the smallest unit of memory the C program can address*.

CHAR_BIT in C and C++ represents the number of bits in a char. It must always be at least 8 due to other requirements on the char type. In practice on all modern general purpose computers it is exactly 8 but some historic or specialist systems may have higher values.

Java has no equivalent of CHAR_BIT or sizeof, there is no need for it as all primitive types in Java are fixed size and the internal structure of objects is opaque to the programmer. If translating this code to Java you can simply replace sizeof(int) * CHAR_BIT - 1 by the fixed value 31.

In this particular code, it is being used to calculate the number of bits in an int. Be aware that this calculation assumes that the int type doesn't contain any padding bits.

Assuming that your compiler chooses to sign extend on bit shifts of signed numbers and assuming your system uses 2s complement representation for negative numbers this means that mask will be 0 for a positive or zero value and -1 for a negative value.

To negate a twos complement number we need to perform a bitwise not and then add one. Equivalently we can subtract one and then bitwise negate it.

Again assuming twos complement representation -1 is represented by all ones, so exclusive or with -1 is equivalent to bitwise negation.

So when v is zero the number is left alone, when v is one it is negated.

Something to be aware of is that signed overflow in C and C++ is undefined behaviour. So using this abs implementation on the most negative value leads to undefined behaviour. This can be fixed by adding casts such that the final line of the program is evaluated in unsigned int.

* Which is usually but not necessarily the same as the smallest unit of memory the hardware can address. An implementation can potentially combine multiple units of hardware-addressable memory into one unit of program-addressable memory or split one unit of hardware addressable memory into multiple units of program-addressable memory.