It is important to note that +, -, *, / bind more tightly than any of the bitwise operators! (see the shift example.)
Use unsigned types such as unsigned int to avoid issues with sign extension.
In the table below maximum is a predefined constant that contains the maximum value for the given type.
type maximum size unsigned char UCHAR_MAX 1 byte unsigned short USHRT_MAX 2 bytes unsigned int UINT_MAX 4 bytes unsigned long int ULONG_MAX 4 or 8 bytes depending on the -m option on the compiler unsigned long long int ULLONG_MAX 8 bytes
The suffix for unsigned long int is UL (can be mixed case). For example 496UL is an unsigned long int constant. 6U is an unsigned int and 8192ULL is an unsigned long long int (64 bit) constant.
Although you can use integer constant notation using hex allows you to "see" what bits you are setting. Hex constants begin with "0x" as in 0xfff for the least significant 12 bits. For an 32 bit string it would be:
0xfff = 00000000000000000000111111111111
0x1 is the least significant bit.
0xaa = 00000000000000000000000010101010
The bitwize and operator is represented by a single &. This performs a bitwize and. For example 0xc & 0xa would give 0x8:
00001100 & 00001010 ----------- 00001000By "bitwize" we mean the operation is done for each bit position in the string. That is for each bit position k in the input strings we AND the bits in the two input strings in position k. For the logical operators, 1 is treated as true and 0 as false.
This can be used for selecting bits. For example select the least significant bit of x:
x & 0x1
Select the right most 5 bits:
x & 0x1f
The term mask is used to refer to a bitstring that is used for selection in some way. For instance:
x = x & maskonly preserves the bits in x where there is a 1 in the mask. This can, of course, be expressed as:
x &= mask
The bitwize or operator is a single vertical bar: | For example 0xc | 0xa would give 0xe:
00001100 | 00001010 ----------- 00001110
This can be used to set bits in bit strings. For example set the second bit of x to 1:
x = x | 0x2
Or it can be used in conjunction with and to join parts of two bit strings. For example set the lower 3 bits of a 32 bit x to the lower 3 bits of y:
x = (x&0xfffffff8) | (y&0x7)
Set the bits in x that are indicated by the mask:
x |= mask
The bitwize exclusive or operator (also known as xor) is a caret: ^ For example 0xc ^ 0xa would give 0x6:
00001100 ^ 00001010 ----------- 00000110
Note that bits are only set if there is a difference in the values of a bit position.
The xor operator can be used to flip bits. For instance if you wanted to flip the last 3 bits of x:
x = x ^ 0x7
More generally: flip the bits that are indicated by the mask:
x ^= mask
Here it is in binary:
10110101 = x ^ 00011111 = mask ----------- 10101010 = new x
You can also use this to swap two strings in a nontraditional way:
x = x ^ y; y = y ^ x; x = x ^ y;
You can use this to swap the parts of a string:
x = x ^ (y & mask); y = y ^ (x & mask); x = x ^ (y & mask);
Here is the swap in binary with spaces put in to make it easier to see where the swap happens:
x = 11011110110 00000011100 1011011011 y = 01100011011 11100110111 0001110101 mask = 00000000000 11111111111 0000000000
x = 11011110110 11100110111 1011011011 y = 01100011011 00000011100 0001110101
The bitwize complement operator is a tilde: ~ For example ~0xc would give 0xf3 in an unsigned char
~ 00001100 ----------- 11110011
Let's revisit the combing of two strings. Or it can be used in conjunction with and to join parts of two bit strings. For example set the lower 3 bits of a 32 bit x to the lower 3 bits of y:
x = (x & ~0x7) | (y & 0x7)
The bitwize right shift operator is: >> and left shift operator is: << For unsigned types the right shift fills with 0. The left shift always fills with zero.
For example 0xc >> 3 would give 0x1:
00001100 >> 3 ----------- 00000001
and 0xc << 3 would give 0x60:
00001100 << 3 ----------- 01100000
Warning: do not try to shift the same number of bits as there are in the type being shifted. This is returns different values on different processors and is not reliable and may not issue an error when it does this! e.g. do not do x<<32 for unsigned int x.
(x>>12)<<12will zero the right most 12 bits of x. This, of course, could be done with a single bitwize and.
To get 21 bits of 1 right justified in the value i.e. 0x1fffff you can do
(1<<21)-1This is a popular idiom.
It is important to note that +, -, *, / bind more tightly than any of the bitwise operators! This means that:
1<<21-1 = 1<<22
To extract bits 4-6 inclusive of x assuming the right most bit is numbered 0:
(x>>4)&0x7this will first position bit number 4 in position 0 and the mask away all but the right most 3 bits giving you what was bits 4-6.
In order to rotate bits left you need to take the bits off the left side and attach them on the right. So for a 32 bit x that you want to rotate by amount r:
It turns out that you can easily compute the Binary Reflected Gray code of a bitstring x:
x ^ (x>>1)Yes, it is that simple.
The degray function is used to decode a number that is in Gray code into a regular number.
degray(gray(x)) == x and gray(degray(x)) == xTo degray is also relatively simple although you now need to know how many bits wide x is. For 32 bit x you need:
x^=(x>>1); x^=(x>>2); x^=(x>>4); x^=(x>>8); x^=(x>>16);
Random number generators (RNG) generally produce a pseudo-random number as a 32 or a 64 bit number depending on the generator. Most require initialization. There are two qualities of a random number generator that are of interest to us: speed and randomness. There is to some degree a tradeoff between these.
A convenient way to use a random number is to use a call that returns a double between 0 and 1. But this often does more work than is necessary for a particular application of the RNG and is therefore slower than it needs to be. In some applications the number of calls to the RNG is sufficiently large that it can be a major part of time used by the application. Here are some examples of using the raw bits returned to speed things up. This requires a reasonably unpatterned random number generator unlike the old UNIX rand() procedure. I use a small random number generator called Flea whose prototype is:
unsigned int flea();
If you want to decide between two things as if you are flipping a fair coin then simply mask a bit out of the random bitstring:
if (flea()&0x1) stuff // uses the least significant bitCheck to be sure your random number generator doesn't have a pattern in the bit position you use (beware linear congruential RNGs).
If you want to chose between k things do not use the mod (%) operator. It is very slow. If you can convert it to a choice between a power of two number of things then use a mask. Say you want to choose between 6 things then try to make it a choice between 8 things and mask off 3 bits.
If you want to choose something with a probability p and you have the chance to choose a p' that close but is k times a power of two then again you can simply mask bits off the RNG.