Applications of bitwise operators in C and their efficiency?

Question

I am new to bitwise operators.

I understand how the logic functions work to get the final result. For example, when you bitwise AND two numbers, the final result is going to be the AND of those two numbers (1 & 0 = 0; 1 & 1 = 1; 0 & 0 = 0). Same with OR, XOR, and NOT.

What I don't understand is their application. I tried looking everywhere and most of them just explain how bitwise operations work. Of all the bitwise operators I only understand the application of shift operators (multiplication and division). I also came across masking. I understand that masking is done using bitwise AND but what exactly is its purpose and where and how can I use it?

Can you elaborate on how I can use masking? Are there similar uses for OR and XOR?

Solution 1

The low-level use case for the bitwise operators is to perform base 2 math. There is the well known trick to test if a number is a power of 2:

if ((x & (x - 1)) == 0) {
    printf("%d is a power of 2\n", x);
}

But, it can also serve a higher level function: set manipulation. You can think of a collection of bits as a set. To explain, let each bit in a byte to represent 8 distinct items, say the planets in our solar system (Pluto is no longer considered a planet, so 8 bits are enough!):

#define Mercury (1 << 0)
#define Venus   (1 << 1)
#define Earth   (1 << 2)
#define Mars    (1 << 3)
#define Jupiter (1 << 4)
#define Saturn  (1 << 5)
#define Uranus  (1 << 6)
#define Neptune (1 << 7)

Then, we can form a collection of planets (a subset) like using |:

unsigned char Giants = (Jupiter|Saturn|Uranus|Neptune);
unsigned char Visited = (Venus|Earth|Mars);
unsigned char BeyondTheBelt = (Jupiter|Saturn|Uranus|Neptune);
unsigned char All = (Mercury|Venus|Earth|Mars|Jupiter|Saturn|Uranus|Neptune);

Now, you can use a & to test if two sets have an intersection:

if (Visited & Giants) {
    puts("we might be giants");
}

The ^ operation is often used to see what is different between two sets (the union of the sets minus their intersection):

if (Giants ^ BeyondTheBelt) {
    puts("there are non-giants out there");
}

So, think of | as union, & as intersection, and ^ as union minus the intersection.

Once you buy into the idea of bits representing a set, then the bitwise operations are naturally there to help manipulate those sets.

Solution 2

One application of bitwise ANDs is checking if a single bit is set in a byte. This is useful in networked communication, where protocol headers attempt to pack as much information into the smallest area as is possible in an effort to reduce overhead.

For example, the IPv4 header utilizes the first 3 bits of the 6th byte to tell whether the given IP packet can be fragmented, and if so whether to expect more fragments of the given packet to follow. If these fields were the size of ints (1 byte) instead, each IP packet would be 21 bits larger than necessary. This translates to a huge amount of unnecessary data through the internet every day.

To retrieve these 3 bits, a bitwise AND could be used along side a bit mask to determine if they are set.

char mymask = 0x80;
if(mymask & (ipheader + 48) == mymask)
  //the second bit of the 6th byte of the ip header is set 

Solution 3

Small sets, as has been mentioned. You can do a surprisingly large number of operations quickly, intersection and union and (symmetric) difference are obviously trivial, but for example you can also efficiently:

1. get the lowest item in the set with x & -x
2. remove the lowest item from the set with x & (x - 1)
3. add all items smaller than the smallest present item
4. add all items higher than the smallest present item
5. calculate their cardinality (though the algorithm is nontrivial)
6. permute the set in some ways, that is, change the indexes of the items (not all permutations are equally efficient)
7. calculate the lexicographically next set that contains as many items (Gosper's Hack)

1 and 2 and their variations can be used to build efficient graph algorithms on small graphs, for example see algorithm R in The Art of Computer Programming 4A.

Other applications of bitwise operations include, but are not limited to,

• Bitboards, important in many board games. Chess without bitboards is like Christmas without Santa. Not only is it a space-efficient representation, you can do non-trivial computations directly with the bitboard (see Hyperbola Quintessence)
• sideways heaps, and their application in finding the Nearest Common Ancestor and computing Range Minimum Queries.
• efficient cycle-detection (Gosper's Loop Detection, found in HAKMEM)
• adding offsets to Z-curve addresses without deconstructing and reconstructing them (see Tesseral Arithmetic)

These uses are more powerful, but also advanced, rare, and very specific. They show, however, that bitwise operations are not just a cute toy left over from the old low-level days.

Solution 4

Example 1

If you have 10 booleans that "work together" you can do simplify your code a lot.

int B1 = 0x01;
int B2 = 0x02;
int B10 = 0x0A;

int someValue = get_a_value_from_somewhere();

if (someValue & (B1 + B10)) {
    // B1 and B10 are set
}

Example 2

Interfacing with hardware. An address on the hardware may need bit level access to control the interface. e.g. an overflow bit on a buffer or a status byte that can tell you the status of 8 different things. Using bit masking you can get down the the actual bit of info you need.

if (register & 0x80) {
    // top bit in the byte is set which may have special meaning.
}

This is really just a specialized case of example 1.

Solution 5

Bitwise operators are particularly useful in systems with limited resources as each bit can encode a boolean. Using many chars for flags is wasteful as each takes one byte of space (when they could be storing 8 flags each).

Commonly microcontrollers have C interfaces for their IO ports in which each bit controls 1 of 8 ports. Without bitwise operators these would be quite difficult to control.

Regarding masking, it is common to use both & and |:

x & 0x0F //ensures the 4 high bits are 0
x | 0x0F //ensures the 4 low bits are 1

View more solutions

Comments

[Sai Maddali]

So lets say I want to extract the most significant 6 bits of a 12 bit number, should I OR that number with '0x0F' and use AND for vice versa (least significant 6 bits)?

[Cameron S]

It depends on what you want the other bits to be. If you want the least significant 4 bits to be 0, then you can AND them with 0xF0. 0000xxxx | 11110000 = 1111xxxx (the x's aren't changed, which is powerful when you ONLY want to change specific bits).

[Patratacus]

I love this practical explanation of the usage. It makes the concept very clear for me especially in terms of usage for micro-controller pins and registers setting.

[jxh]

@MindaugasBernatavičius: "Pluto was discovered by Clyde Tombaugh in 1930 as the ninth planet from the Sun. After 1992, its status as a planet was questioned following the discovery of several objects of similar size in the Kuiper belt. In 2005, Eris, a dwarf planet in the scattered disc which is 27% more massive than Pluto, was discovered. This led the International Astronomical Union (IAU) to define the term "planet" formally in 2006, during their 26th General Assembly. That definition excluded Pluto and reclassified it as a dwarf planet." Wikipedia