1852

40
+22  Q:

## Real world use cases of bitwise operators

What are some real world use cases of the following bitwise operators?

• AND
• XOR
• NOT
• OR
A:

I use them for multi select options, this way I only store one value instead of 10 or more

+13  A:

Low-level programming is a good example. You may, for instance, need to write a specific bit to a memory-mapped register to make some piece of hardware do what you want it to:

``````volatile uint32_t *register = (volatile uint32_t *)0x87000000;
uint32_t          value;
uint32_t          set_bit   = 0x00010000;
uint32_t          clear_bit = 0x00001000;

value = *register;            // get current value from the register
value = value & ~clear_bit;   // clear a bit
value = value | set_bit;      // set a bit
*register = value;            // write it back to the register
``````

Also, `htonl()` and `htons()` are implemented using the `&` and `|` operators (on machines whose endianness doesn't match network order):

``````#define htons(a) ((((a) & 0xff00) >> 8) | \
(((a) & 0x00ff) << 8))

#define htonl(a) ((((a) & 0xff000000) >> 24) | \
(((a) & 0x00ff0000) >>  8) | \
(((a) & 0x0000ff00) <<  8) | \
(((a) & 0x000000ff) << 24))
``````
Not everyone speaks in machine. Whats your second example doing?
`htons()` and `htonl()` are POSIX functions to swap a `short` or a `long` from the host (`h`) endianness to the network (`n`) byte order.
You can use a similar method to do a bit-reversal in O(logN) operations.
+7  A:

I just used bitwise-XOR (`^`) about three minutes ago to calculate a checksum for serial communication with a PLC...

+3  A:

You can use them as a quick and dirty way to hash data.

``````int a = 1230123;
int b = 1234555;
int c = 5865683;
int hash = a ^ b ^ c;
``````
+12  A:

I use them to get RGB(A) values from packed colorvalues, for instance.

And it does it really quickly!
In C# it's one of those cases where it really is the best solution, for readability and speed.
+5  A:

Encryption is all bitwise operations.

Really? Encryption implementations are likely to use bitwise ops, but encryption algorithms are usually described in numeric terms and not in terms of bit representations.
So what do you do with algorithms other than implement them? I'm curious.
@Constantin: See, for example, the description of how DES is implemented: (http://en.wikipedia.org/wiki/Data_Encryption_Standard#The_Feistel_.28F.29_function
@recursive, If you're asking about me personally - i neither design cryptographic algorithms nor implement them. But people do many things, like analyzing them for theoretical weaknesses.
@Constantin: take a look at this, this is just one example amongst many as to how (part of) cryptographic algorithms are typically described:http://en.wikipedia.org/wiki/Substitution_box
Or, for those interested in a readable description of (i think it's AES): http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html
+3  A:

Base64 encoding is an example. Base64 encoding is used to represent binary data as a printable characters for sending over email systems (and other purposes). Base64 encoding converts a series of 8 bit bytes into 6 bit character lookup indexes. Bit operations, shifting, and'ing, or'ing, not'ing are very useful for implementing the bit operations necessary for Base64 encoding and decoding.

This of course is only 1 of countless examples.

+5  A:

Bitwise & is used to mask/extract a certain part of a byte.

1 Byte variable

`````` 01110010
&00001111 Bitmask of 0x0F to find out the lower nibble
--------
00000010
``````

Specially the shift operator (<< >>) are often used for calculations.

+10  A:

When I have a bunch of boolean flags, I like to store them all in an int.

I get them out using bitwise-AND. For example:

``````int flags;
if (flags & 0x10) {
// Turn this feature on.
}

if (flags & 0x08) {
// Turn a second feature on.
}
``````

etc.

Hopefully those are actually constants in your real code and not magic numbers :)
One example of using boolean flags in the non low-level world is doing stuff with various GUI platforms. For instance you might use my_button.Style |= STYLE_DISABLED to turn it off.
A:

When you only want to change some bits of a microcontroller's Outputs, but the register to write to is a byte, you do something like this (pseudocode):

``````char newOut = OutRegister & 0b00011111 //clear 3 msb's
newOut = newOut | 0b10100000 //write '101' to the 3 msb's
OutRegister = newOut //Update Outputs
``````

Of course, many microcontrollers allow you to change each bit individually...

what language is this supposed to be?
@Carson: No language, this is pseudocode. When I've actually done that a few years ago it was Assembly, but I suppose it's easy to do it in C. Thanks for the heads up, I'll update to make it clearer
I edited the answer to change the comments so the highlighting wasn't so fudged. And I see, I thought it might be C but you used 0b... notation which I _wish_ was available in C.
+7  A:

Here's some common idioms dealing with flags stored as individual bits.

``````enum CDRIndicators {
Local = 1 << 0,
External = 1 << 1,
CallerIDMissing = 1 << 2,
Chargeable = 1 << 3
};

unsigned int flags = 0;
``````

Set the Chargeable flag:

``````flags |= Chargeable;
``````

Clear CallerIDMissing flag:

``````flags &= ~CallerIDMissing;
``````

Test whether CallerIDMissing and Chargeable are set:

``````if((flags & (CallerIDMissing | Chargeable )) == (CallerIDMissing | Chargeable)) {

}
``````
+1 for setting the enum values the correct way :-)
+1  A:

I've seen them used in role based access control systems.

A:

Whenever I first started C programming, I understood truth tables and all that, but it didn't all click with how to actually use it until I read this article http://www.gamedev.net/reference/articles/article1563.asp (which gives real life examples)

No, it's not the same. In C, if `x == 1` and `y == 2`, then `x || y` evaluates to 1, and `x | y` evaluates to 0. Nor do I see why `x^true` is superior to `!x` in any way. It's more typing, less idiomatic, and if `x` happens not to be a `bool` it's unreliable.
oh wait.. yea, that's dumb on my part.. I can't seem to think straight today.
x | y evaluates to 3 (edit: nvm, I see that you were reffering to something edited away!)
+35  A:
• Bit fields (flags)
They're the most efficient way of representing something whose state is defined by several "yes or no" properties. ACLs are a good example; if you have let's say 4 discrete permissions (read, write, execute, change policy), it's better to store this in 1 byte rather than waste 4. These can be mapped to enumeration types in many languages for added convenience.

• Communication over ports/sockets
Always involves checksums, parity, stop bits, flow control algorithms, and so on, which usually depend on the logic values of individual bytes as opposed to numeric values, since the medium may only be capable of transmitting one bit at a time.

• Compression, Encryption
Both of these are heavily dependent on bitwise algorithms. Look at the deflate algorithm for an example - everything is in bits, not bytes.

• Finite State Machines
I'm speaking primarily of the kind embedded in some piece of hardware, although they can be found in software too. These are combinatorial in nature - they might literally be getting "compiled" down to a bunch of logic gates, so they have to be expressed as `AND`, `OR`, `NOT`, etc.

• Graphics There's hardly enough space here to get into every area where these operators are used in graphics programming. `XOR` (or `^`) is particularly interesting here because applying the same input a second time will undo the first. Older GUIs used to rely on this for selection highlighting and other overlays, in order to eliminate the need for costly redraws. They're still useful in slow graphics protocols (i.e. remote desktop).

Those were just the first few examples I came up with - this is hardly an exhaustive list.

Pretty vague...
OK, I made it less vague. ;)
A:

I often use bitwise operations for storing combinations of options in a single integer.

int options = 0;

where OPTION1 might be defined as 1, OPTION2 as 2, OPTION3 as 4, OPTION4 as 8, OPTION5 as 16, ...

`void addOption(int option)` would use the '|' operator to add an option to options.

`boolean hasOption(int option)` would use the '&' operator to test for the option within options.

A:

There is a real world use in my question here -

When consuming a WM_KEYDOWN message in the windows C api bit 30 specifies the previous key state. The value is 1 if the key is down before the message is sent, or it is zero if the key is up

+2  A:

In the abstracted world of today's modern language, not too many. File IO is an easy one that comes to mind, though that's exercising bitwise operations on something already implemented and is not implementing something that uses bitwise operations. Still, as an easy example, this code demonstrates removing the read-only attribute on a file (so that it can be used with a new FileStream specifying FileMode.Create) in c#:

``````//Hidden files posses some extra attibutes that make the FileStream throw an exception
//even with FileMode.Create (if exists -> overwrite) so delete it and don't worry about it!
if(File.Exists(targetName))
{
FileAttributes attributes = File.GetAttributes(targetName);

File.Delete(targetName);
}
``````

As far as custom implementations, here's a recent example: I created a "message center" for sending secure messages from one installation of our distributed application to another. Basically, it's analogous to email, complete with Inbox, Outbox, Sent, etc, but it also has guaranteed delivery with read receipts, so there are additional subfolders beyond "inbox" and "sent." What this amounted to was a requirement for me to define generically what's "in the inbox" or what's "in the sent folder". Of the sent folder, I need to know what's read and what's unread. Of what's unread, I need to know what's received and what's not received. I use this information to build a dynamic where clause which filters a local datasource and displays the appropriate information.

Here's how the enum is put together:

``````    public enum MemoView :int
{
InboundMemos = 1,                   //     0000 0001
InboundMemosForMyOrders = 3,        //     0000 0011
SentMemosAll = 16,                  //     0001 0000
Outbox = 272,                       //0001 0001 0000
OutBoxErrors = 784                  //0011 0001 0000
}
``````

Do you see what this does? By anding (&) with the "Inbox" enum value, InboundMemos, I know that InboundMemosForMyOrders is in the inbox.

Here's a boiled down version of the method that builds and returns the filter that defines a view for the currently selected folder:

``````    private string GetFilterForView(MemoView view, DefaultableBoolean readOnly)
{
string filter = string.Empty;
if((view & MemoView.InboundMemos) == MemoView.InboundMemos)
{
filter = "<inbox filter conditions>";

if((view & MemoView.InboundMemosForMyOrders) == MemoView.InboundMemosForMyOrders)
{
filter += "<my memo filter conditions>";
}
}
else if((view & MemoView.SentMemosAll) == MemoView.SentMemosAll)
{
//all sent items have originating system = to local
filter = "<memos leaving current system>";

if((view & MemoView.Outbox) == MemoView.Outbox)
{
...
}
else
{
//sent sub folders
filter += "<all sent items>";

{
{
}
else
}
}
}

return filter;
}
``````

Extremely simple, but a neat implementation at a level of abstraction that doesn't typically require bitwise operations.

+1  A:

They are mostly used for bitwise operations (surprise). Here are a few real-world examples found in PHP codebase.

Character encoding:

``````if (s <= 0 && (c & ~MBFL_WCSPLANE_MASK) == MBFL_WCSPLANE_KOI8R) {
``````

Data structures:

``````ar_flags = other->ar_flags & ~SPL_ARRAY_INT_MASK;
``````

Database drivers:

``````dbh->transaction_flags &= ~(PDO_TRANS_ACCESS_MODE^PDO_TRANS_READONLY);
``````

Compiler implementation:

``````opline->extended_value = (opline->extended_value & ~ZEND_FETCH_CLASS_MASK) | ZEND_FETCH_CLASS_INTERFACE;
``````
A:

I've seen it in a few game development books as a more efficient way to multiply and divide.

``````2 << 3 == 2 * 8
32 >> 4 == 32 / 16
``````
Those books must be old.
Is it no longer more efficient due to improvements in compilers or processors?
@Seth: It is no longer necessarily more efficient due to improvements in processors. Specifically superscalar CPUs and even more so if the CPU implements out of order execution. But it is still a useful idiom for small microcontrollers although all compilers I've used does this automatically even with optimizations turned off.
I wanted to add that it takes the `floor` of the division. `5>>1==2, not 2.5: 00000101->00000010`
+2  A:

& = AND:
You are defining the specific bits which should be displayed or not displayed. 0x0 & x will clear all bits in a byte while 0xFF will not change x. 0x0F will display the bits in the lower nibble.

Conversion:
To cast shorter variables into longer ones with bit identity it is necessary to adjust the bits because -1 in an int is 0xFFFFFFFF while -1 in a long is 0xFFFFFFFFFFFFFFFF. To preserve the identity you apply a mask after conversion.

|=OR
Set bits. The bits will be set indepently if they are already set. Many datastructures (bitfields) have flags like IS_HSET = 0, IS_VSET = 1 which can be indepently set. To set the flags, you apply IS_HSET | IS_VSET (In C and assembly this is very convenient to read)

^=XOR
Find bits which are the same or different.

~= NOT
Flip bits.

It can be shown that all possible local bit operations can be implemented by these operations. So if you like you can implement an ADD instruction solely by bit operations.

Some wonderful hacks:

The following is a link that gives excellent examples of using bitwise operators in AS3 for super fast math operations (but it could likely be applied to most languages): http://lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math/
I think "NOT" should be `= ~`, not `|=`, which is OR.
Right. Corrected
A:

See here for some interesting uses.

+1  A:

it can also be handy in a sql relational model, let's say you have the following tables: BlogEntry, BlogCategory

traditonally you could create a n-n relationship between them using a BlogEntryCategory table or when there are not that much BlogCategory records you could use one value in BlogEntry to link to multiple BlogCategory records just like you would do with flagged enums, in most RDBMS there are also a very fast operators to select on that 'flagged' column...

Interesting example!
+4  A:

Is it odd?

``````(value & 0x1) > 0
``````

Is it divisible by two (even)?

``````(value & 0x1) == 0
``````
@leeeroy - True enough. Added some parens.
+1  A:

Is a number `x` a power of 2? (Useful for example in algorithms where a counter is incremented, and an action is to be taken only logarithmic number of times)

``````(x & (x - 1)) == 0
``````

Which is the highest bit of an integer `x`? (This for example can be used to find the minimum power of 2 that is larger than `x`)

``````x |= (x >>  1);
x |= (x >>  2);
x |= (x >>  4);
x |= (x >>  8);
x |= (x >> 16);
return x - (x >>> 1); // ">>>" is unsigned right shift
``````

Which is the lowest `1` bit of an integer `x`? (Helps find number of times divisible by 2.)

``````x & -x
``````
A:

I use them as an option handlers, e.g. in Acces Control Lists to describe specific resources.

Edit:
A:

I wrote a small wiki article a while back showing a binary writer/reader. It works on the bit level and shows how bitwise operators can be used to pack data. That would probably be a "real world" example since it has application in games.

+3  A:

I've used bitwise operations in implementing a security model for a CMS. It had pages which could be accessed by users if they were in appropriate groups. A user could be in multiple groups, so we needed to check if there was an intersection between the users groups and the pages groups. So we assigned each group a unique power-of-2 identifier, e.g.:

``````Group A = 1 --> 00000001
Group B = 2 --> 00000010
Group C = 3 --> 00000100
``````

We OR these values together, and store the value (as a single int) with the page. E.g. if a page could be accessed by groups A & B, we store the value 3 (which in binary is 00000011) as the pages access control. In much the same way, we store a value of ORed group identifiers with a user to represent which groups they are in.

So to check if a given user can access a given page, you just need to AND the values together and check if the value is non-zero. This is very fast as this check is implemented in a single instruction, no looping, no database round-trips.

A:

I was always under the assumption that bitwise operations are fairly simple operations to be performed, so when running time is crucial a solution which is implemented via bitsets can improve running time by a constant amount, algorithm depending.

A:

Another real world application in the database world is MySQL which has a datatype called SET.

Bitwise operators are by the DBMS to store the SET datatype. Set can save space.

``````Element    SET Value    Decimal Value
Travel      00000001    1
Sports      00000010    2
Dancing    00000100    4
Fine Dining   00001000  8
``````
+1  A:

I don't think this counts as bitwise, but ruby's Array defines set operations through the normal integer bitwise operators. So `[1,2,4] & [1,2,3] # => [1,2]`. Similarly for `a ^ b #=> set difference` and `a | b #=> union`.

A:

I use them to implement fast BCD calculations (accountants and auditors get upset with fp rounding).

A:

We use Bitwise Flags to make the session smaller for login permissions on our internal website.

+1  A:

I'm suprised no one picked the obvious answer for the Internet age. Calculating valid network addresses for a subnet.

+1  A:

Nobody seems to have mentioned fixed point maths.

(Yeah, I'm old, ok?)

A:

A very specific example, but I used them to make my sudoku solver run faster (I was having a competition with a friend)

Each column, row and 3x3 was represented as an unsigned integer and as I set numbers I'd flag the appriate bit for the number set in the relevent column,row and 3x3 square.

This then made it very easy to see what possible numbers I could place in a given square since I would OR together the right column,row and 3x3 square and then NOT this to leave me with a mask that represented the possible legal values for a given position.

Hope that makes sense.

+1  A:

This is an example to read colours from a bitmap image in byte format

``````byte imagePixel = 0xCCDDEE; /* Image in RRGGBB format R=Red, G=Green, B=Blue */

//To only have red
byte redColour = imagePixel & 0xFF0000; /*Bitmasking with AND operator */

//Now, we only want red colour
redColour = (redColour >> 24) & 0xFF;  /* This now returns a red colour between 0x00 and 0xFF.
``````

I hope this tiny examples helps....

A:

RAID 5/6 !! You are probably using it right now when you interact with this website! Isn't that about as real as it gets!?

A:

Nobody's mentioned collections yet. Sometimes you have a smallish collection of possible values, say only 10 or 20 possible values, and you want to keep some of them in a set. Sure you can use a regular `Set` implementation which will most likely use a backing hashtable. But since the set of possible values is so small this is really just a waste of time and space. Instead, you can store the set in a single `int` or `long` value which is exactly what the java `EnumSet` does if I remember correctly.

A:

If you ever want to calculate your number mod(%) a certain power of 2, you can use `yourNumber & 2^N-1`, which in this case is the same as `yourNumber % 2^N`.

``````number % 16 = number & 15;
number % 128 = number & 127;
``````

This is probably only useful being an alternative to modulus operation with a very big dividend that is 2^N... But even then its speed boost over the modulus operation is negligible in my test on .NET 2.0. I suspect modern compilers already perform optimizations like this. Anyone know more about this?

A:

A common use is for alignment e.g I need my data aligned on 4-byte or 16-byte boundaries.This is very common with RISC processors where an unaligned load/store is either expensive ( because it triggers an exception handler that then needs to fix up the non-aligned load ) or not allowed at all.

For any alignment that is a power of 2, the next aligned pos can be calculated as follows :

``````aligned_offset = alignment + ((current_offset - 1) & ~(alignment - 1))
``````

So in the case of 4 byte alignment and a current offset of 9 then :

``````aligned_offset = 4 + ((9-1) & ~(4-1)) = 4 + (8 & 0xFFFFFFFC) = 4+ 8  = 12
``````

so the next 4 byte aligned offset would be 12