20

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?

9
  • @Anto - An easy example would be sending 256Kb worth of data at a rate of 256 words at a time ( 4096 bytes ) to a client.
    – Ramhound
    Apr 5, 2011 at 18:13
  • 1
    "Without using any equality operator, create a function which returns true when two values are equal" - in C: return !(x-y);? I dunno
    – Andrew
    Apr 5, 2011 at 18:39
  • @Andrew: That is a solution, but you can do it with bitwise operators as well.
    – Anto
    Apr 5, 2011 at 18:49
  • 20
    "These don't get used though very much" - Sure about that? I use them all of the time. We don't all work in your problem domain.
    – Ed S.
    Apr 5, 2011 at 20:06
  • 2
    Not enough for a full answer, but try reading the top 4 bits of a byte without bit fiddling and then consider that some data formats are very tightly packed. Apr 6, 2011 at 1:39

15 Answers 15

54

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.

8
  • 1
    +1 for your rather comprehensive list, which you even seem to be adding to
    – Anto
    Apr 5, 2011 at 18:24
  • 28
    +1. @Anto: This list is nowhere near comprehensive. A comprehensive list of use cases for bitwise operators in systems programming would be as long as a comprehensive list for SQL queries in business applications. Fun fact: I use bitwise operations all the time, but haven't written an SQL statement in years ;-)
    – nikie
    Apr 5, 2011 at 18:29
  • 4
    @nikie: And I write SQL all the time, but have not used bitwise operators in years! :) Apr 5, 2011 at 18:51
  • 3
    I work in embedded systems - bitwise operators are bread and butter stuff. Used everyday without any thought at all. Apr 5, 2011 at 23:44
  • 9
    If I occasionally use bitshifting in SQL, do I get a prize?
    – Ant
    Apr 6, 2011 at 8:19
13

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.

12

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 );
3
  • Show this example in practice? A code snippet?
    – Anto
    Apr 5, 2011 at 18:07
  • A better example might be processing 16-bit (4.5bpc) or 30-bit (10bpc) RGB values.
    – greyfade
    Apr 5, 2011 at 18:10
  • @grey, feel free to add such examples.
    – user1249
    Apr 5, 2011 at 18:11
6

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).

1
  • +1 For those comments, even if they aren't yours. Made me chuckle.
    – Bassinator
    Apr 9, 2015 at 1:30
4

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.

7
  • 1
    Just be careful when dividing with rounding up or down etc. Shifting does not account for that, so I've found it actually better practice to use a divide in code when I mean a divide and let the compiler optimise it into a shift and add for me. Apr 6, 2011 at 6:24
  • @Daemin: I am working with integers when I use this technique. The default behavior for integer division in C and C++ is truncation toward zero; therefore, shifting an integer right by a power of two produces the same result as dividing an integer by a power of two. Apr 6, 2011 at 21:59
  • 1
    @bit-twiddler Right shift does not work the same way as division for negative numbers. Apr 7, 2011 at 6:24
  • @Daemin: You seem to be hell bent on proving me wrong. First, you throw up the rounding problem. When I repudiate that claim by stating that division in C and C++ truncates toward zero, you throw out the signed integer issue. Where did I say that I was applying the shift operator to signed two's complement negative integers? With that said, one can still use the shift operator to divide by a power of two. However, because C and C++ perform and arithmetic right shift instead of a plain old right shift, one must first check to see if value is negative. If the value is negative, Apr 7, 2011 at 14:45
  • 1
    Exactly, be careful when using shifting as a substitute for multiplication and division as there are subtle differences. No more no less. Apr 8, 2011 at 7:40
3

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."

3
  • xkcd.com/378 comes to mind.
    – Maxpm
    Apr 6, 2011 at 5:08
  • Bit operators are useful to this very day. The fact that in your domain they're not used does not make it unused or even not used very often. Here's a simple example: try and implement AES without bit operators. That's one off-the-cuff example of something that's done in most computers on a daily basis hundreds or thousands of times per day. Apr 6, 2011 at 14:40
  • Encoding/decoding data without using bit-wise operators is painful at best. For example, adding MIME attachments to a message requires us to be able to handle three-to-four coding of data (a.k.a. radix64 coding). Apr 7, 2011 at 15:17
2

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);
3
  • Although not sure DES is recommended these days :P
    – Armand
    Apr 5, 2011 at 20:25
  • @Alison: No, but the encryption algorithms that have replaced it involve even more bit manipulation operations, I think. :-) Apr 5, 2011 at 21:12
  • @Alison - of course, but TripleDES is just DES done 3 times with 3 times the key bits. Apr 5, 2011 at 22:55
2

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.

2

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.

1

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.

1

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.

1

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.

1

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.

0

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
//...
0

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;

Not the answer you're looking for? Browse other questions tagged or ask your own question.