Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
@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 '11 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 Arnold Apr 5 '11 at 18:39
    
@Andrew: That is a solution, but you can do it with bitwise operators as well. –  Anto Apr 5 '11 at 18:49
19  
"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 '11 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. –  Brendan Long Apr 6 '11 at 1:39
show 4 more comments

closed as too broad by MichaelT, gnat, Bart van Ingen Schenau, GlenH7, World Engineer Apr 8 at 0:09

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

15 Answers

up vote 49 down vote accepted

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.

share|improve this answer
1  
+1 for your rather comprehensive list, which you even seem to be adding to –  Anto Apr 5 '11 at 18:24
27  
+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 '11 at 18:29
4  
@nikie: And I write SQL all the time, but have not used bitwise operators in years! :) –  FrustratedWithFormsDesigner Apr 5 '11 at 18:51
3  
I work in embedded systems - bitwise operators are bread and butter stuff. Used everyday without any thought at all. –  quickly_now Apr 5 '11 at 23:44
9  
If I occasionally use bitshifting in SQL, do I get a prize? –  Ant Apr 6 '11 at 8:19
show 3 more comments

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;
share|improve this answer
add comment

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.

share|improve this answer
add comment

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
//...
share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
xkcd.com/378 comes to mind. –  Maxpm Apr 6 '11 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. –  JUST MY correct OPINION Apr 6 '11 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). –  bit-twiddler Apr 7 '11 at 15:17
add comment

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.

share|improve this answer
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. –  Daemin Apr 6 '11 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. –  bit-twiddler Apr 6 '11 at 21:59
1  
@bit-twiddler Right shift does not work the same way as division for negative numbers. –  Daemin Apr 7 '11 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, –  bit-twiddler Apr 7 '11 at 14:45
    
(cont) one must convert the value to positive while keeping track of the sign. e.g., int q = -5; int n = 3; int negative = q < 0; q = negative ? -q : q; q >>= n; q = negative ? -q : q; –  bit-twiddler Apr 7 '11 at 15:05
show 2 more comments

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

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

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.

share|improve this answer
add comment

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