What are bit operators good for? [closed]

Question

Programming languages often come with various bit operators (e.g. bitwise left- and right shift, bitwise AND, OR, XOR...). These don't get used though very much, or at least such has my experience been. They are sometimes used in programming challenges or interview questions, or the solution migh require them, e.g.:

• Without using any equality operator, create a function which returns true when two values are equal
• Without using a third variable, swap the value of two variables

These then again, probably have few real world uses. I guess that they should be faster because they directly manipulate memory on a low level.

Why are such found in most programming languages? Any real world use cases?

Answer 1

No, they have many real-world applications, and are fundamental operations on computers.

They are used for

• Juggling blocks of bytes around that don't fit in the programming languages data types
• Switching encoding back and forth from big to little endian.
• Packing 4 6bit pieces of data into 3 bytes for some serial or usb connection
• Many image formats have differing amounts of bits assigned to each color channel.
• Anything involving IO pins in embedded applications
• Data compression, which often does not have data fit nice 8-bit boundaries.\
• Hashing algorithms, CRC or other data integrity checks.
• Encryption
• Psuedorandom number generation
• Raid 5 uses bitwise XOR between volumes to compute parity.
• Tons more

In fact, logically, all operations on a computer ultimately boil down to combinations of these low level bitwise operations, taking place within the electrical gates of the processor.

Answer 2

Because they're fundamental operations.

By the same line of thought, you could argue that addition has few real-world uses, since it can be replaced completely with subtraction (and negation) and multiplication. But we keep addition because it's a fundamental operation.

And don't think for a moment that just because you haven't seen much need for bitwise operations doesn't mean they're not used very often. Indeed, I've used bitwise ops in nearly every language I've used for things like bit masking.

Off the top of my head, I've used bitwise ops for image processing, bitfields and flags, text processing (e.g., all characters of a particular class often share a common bit pattern), encoding and decoding serialized data, decoding VM or CPU opcodes, and so on. Without bitwise ops, most of these tasks would require many times more complex operations to perform the task less reliably or with poorer readability.

For example:

// Given a 30-bit RGB color value as a 32-bit int
// A lot of image sensors spit out 10- or 12-bit data
// and some LVDS panels have a 10- or 12-bit format
b = (color & 0x000003ff);
g = (color & 0x000ffc00) >> 10;
r = (color & 0x3ff00000) >> 20;

// Going the other way:
color = ((r << 20) & 0x3ff00000) | ((g << 10) & 0x000ffc00) | (b & 0x000003ff);

Decoding CPU instructions for RISC-type CPUs (such as when emulating another platform) requires extracting portions of a large value as above. Sometimes, doing these operations with multiplication and division and modulo, etc., can be as much as ten times slower as the equivalent bitwise ops.

Answer 3

A typical example is extracting the individual colors from a 24 bit RGB value and back.

---

EDIT: From http://www.docjar.com/html/api/java/awt/Color.java.html

    value =  ((int)(frgbvalue[2]*255 + 0.5))    |
                (((int)(frgbvalue[1]*255 + 0.5)) << 8 )  |
                (((int)(frgbvalue[0]*255 + 0.5)) << 16 ) |
                (((int)(falpha*255 + 0.5)) << 24 );

Answer 4

Here's a real world example you'll find in Quake 3, Quake 4. Doom III. All those games that used the Q3 engine.

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

(To understand that code you need to understand how floating point numbers are stored, I definitely can't elaborate on that)

In terms of use, unless you are in fields that require bit shifting such as networking or graphics, then you may find their purpose slightly academic. But still interesting (to me atleast).

Answer 5

Shifting is faster than multiplying or dividing by a power of two. For example, a <<= 2 multiplies a by 4. Conversely, a >>= 2 divides a by four. One can also bit-bang data out to a device using the bit-wise operators. For example, we can send N serial data streams out of an N pin port using shift, xor, and "and" operations inside of N loops. Anything that can be accomplished in digital logic can also be accomplished on software and vise versa.

Answer 6

Long long ago, bit operators were useful. Today they are less so. Oh they aren't entirely useless, but it's been a long time since I've seen one used that should have been used.

In 1977 I was an assembly language programmer. I was convinced assembler was the only true language. I was certain that language like Pascal were for academic weenies who never had to get anything real done.

Then I read "The C Programming Language" by Kernighan and Ritchie. It changed my mind completely. The reason? It had bit operators! It was an assembly language! It just had a different syntax.

Back in those days I couldn't conceive of writing code without ands, ors, shifts, and rotates. Nowadays I almost never use them.

So, the short answer to your question is: "Nothing." But that's not quite fair. So the longer answer is: "Mostly nothing."

Answer 7

Encryption

I suggest taking a look at a very small snippet from the DES encryption algorithm:

temp = ((left >>> 1) ^ right) & 0x55555555; right ^= temp; left ^= (temp << 1);
temp = ((right >>> 8) ^ left) & 0x00ff00ff; left ^= temp; right ^= (temp << 8);
temp = ((right >>> 2) ^ left) & 0x33333333; left ^= temp; right ^= (temp << 2);
temp = ((left >>> 16) ^ right) & 0x0000ffff; right ^= temp; left ^= (temp << 16);
temp = ((left >>> 4) ^ right) & 0x0f0f0f0f; right ^= temp; left ^= (temp << 4);

Answer 8

A lot of good answers, so I won't repeat those uses.

I use them quite a lot in managed code (C# / .Net), and it's nothing to do with space saving, high performance or clever bit shifting algorithms. Sometimes some logic is just well suited to storing data in this way. I often use them when I have an enum but the instances can simultaneously take multiple values from that enum. I can't post an example of code from work, but a quick google for "Flags enum" ("Flags" is the C# way of defining an enum to be used in a bitwise way) gives this nice example: http://www.dotnetperls.com/enum-flags.

Answer 9

There is also bit parallel computing. If your data is only 1's and 0's, you can pack 64 of them into an unsigned long long word, and get 64way parallel operations. Genetic information is two bits (representing the AGCT encoding of DNA), and if you can do the various computations in bit parallel fashion you can do a lot more than if you don't. Not to mention the density of data in memory -if memory, or disk capacity, or communications bandwidth is limited implies that compression/decompression should be considered. Even low precison integers, which show up in areas like image processing, can take advantage of tricky bit parallel computing. It is a whole art unto itself.

Answer 10

Why are they found?

Well that is probably because they correspond to assembly instructions and sometimes they are just useful for things in higher level languages. The same thing applies to the dreaded GOTO which corresponds to the JMP assembly instruction.

What are their uses?

Really there are just to many uses to name so I'll just give a recent, albeit highly localized, usage. I work a lot with 6502 assembly and I was working on a small application that converts memory addresses, values, compare values etc. into codes that can be used for the GameGenie device (Basically a cheat application for the NES). The codes are created by some bit manipulation.

Answer 11

Many programmers these days are used to computers with near infinite memory.

But some of use still program tiny microcontrollers where every bit counts (when you only have 1k or less RAM for instance), and the bitwise operators allows a programmer to use those bits one-at-a-time instead of wasting some much larger programming abstraction entity than might be needed to hold some state required by the algorithm. The IO on those devices may also require being read or controlled on a bitwise bases.

The "real world" has far far more of those tiny microcontrollers than servers or PCs.

For pure theoretical CS types, Turing machines are all about bits of state.

Answer 12

Just one more of many possible uses of the bitwise operators ...

The bitwise operators can also help make your code more readable. Consider the following function declaration ....

int  myFunc (bool, bool, bool, bool, bool, bool, bool, bool);

...

myFunc (false, true, false, false, false, true, true, false);

It is very easy to forget which boolean parameter means what when writing or even reading the code. It is also easy to lose track of your counting. Such a routine can be cleaned up.

/* More descriptive names than MY_FLAGx would be better */
#define MY_FLAG1    0x0001
#define MY_FLAG2    0x0002
#define MY_FLAG3    0x0004
#define MY_FLAG4    0x0008
#define MY_FLAG5    0x0010
#define MY_FLAG6    0x0020
#define MY_FLAG7    0x0040
#define MY_FLAG8    0x0080

int  myFunc (unsigned myFlags);

...

myFunc (MY_FLAG2 | MY_FLAG6 | MY_FLAG7);

With more descriptive flag names, it becomes much more readable.

Answer 13

If you know anything about Unicode, you're probably familiar with UTF-8. It uses a bunch of bit tests, shifts and masks to pack the 20 bits code point into 1 to 4 bytes.

Answer 14

I'm not using them often but sometimes they come in handy. Enum handling comes to mind.

Example:

enum DrawBorder{None = 0, Left = 1, Top = 2, Right = 4, Bottom = 8}

DrawBorder drawBorder = DrawBorder.Left | DrawBorder.Right;//Draw right & left border
if(drawBorder & DrawBorder.Left == DrawBorder.Left)
  //Draw the left border
if(drawBorder & DrawBorder.Top == DrawBorder.Top)
  //Draw the top border
//...

Answer 15

Not sure if this usage has been noted yet:

I see OR quite a lot when working with the illumos (openSolaris) source code to reduce multiple return values to 0 or 1, e.g.

int ret = 0;
ret |= some_function(arg, &arg2); // returns 0 or 1
ret |= some_other_function(arg, &arg2); // returns 0 or 1
return ret;