Take the 2-minute tour ×

I must say I have never had cause to use bitwise operators, but I am sure there are some operations that I have performed that would have been more efficiently done with them. How have "shifting" and "OR-ing" helped you solve a problem more efficiently?

share|improve this question

12 Answers 12

up vote 14 down vote accepted

See the famous Bit Twiddling Hacks
Most of the multiply/divide ones are unnecessary - the compiler will do that automatically and you will just confuse people.

But there are a bunch of, 'check/set/toggle bit N' type hacks that are very useful if you work with hardware or communications protocols.

share|improve this answer

Using bitwise operations on strings (characters)

Convert letter to lowercase:

  • OR by space => (x | ' ')
  • Result is always lowercase even if letter is already lowercase
  • eg. ('a' | ' ') => 'a' ; ('A' | ' ') => 'a'

Convert letter to uppercase:

  • AND by underline => (x & '_')
  • Result is always uppercase even if letter is already uppercase
  • eg. ('a' & '_') => 'A' ; ('A' & '_') => 'A'

Invert letter's case:

  • XOR by space => (x ^ ' ')
  • eg. ('a' ^ ' ') => 'A' ; ('A' ^ ' ') => 'a'

Letter's position in alphabet:

  • AND by chr(31)/binary('11111')/(hex('1F') => (x & "\x1F")
  • Result is in 1..26 range, letter case is not important
  • eg. ('a' & "\x1F") => 1 ; ('B' & "\x1F") => 2

Get letter's position in alphabet (for Uppercase letters only):

  • AND by ? => (x & '?') or XOR by @ => (x ^ '@')
  • eg. ('C' & '?') => 3 ; ('Z' ^ '@') => 26

Get letter's position in alphabet (for lowercase letters only):

  • XOR by backtick/chr(96)/binary('1100000')/hex('60') => (x ^ '`')
  • eg. ('d' ^ '`') => 4 ; ('x' ^ '`') => 25

Note: using anything other than the english letters will produce garbage results

share|improve this answer
How did you know i would be interested .... :) –  Baba Apr 23 '13 at 18:41
@Ka: Does this works in javascript too? I tried these in firebug's console but I always got 0. –  Razort4x May 6 '13 at 7:01
@Razort4x it works in JS via fromCharCode and charCodeAt. eg. String.fromCharCode("a".charCodeAt(0) & 95); –  CSᵠ May 7 '13 at 10:13

I have not read the book (yet), but I have been told that the Book Hacker's Delight shows a number of tricks in working with bits.

share|improve this answer

You can compress data, e.g. a collection of integers:

  • See which integer values appear more frequently in the collection
  • Use short bit-sequences to represent the values which appear more frequently (and longer bit-sequences to represent the values which appear less frequently)
  • Concatenate the bits-sequences: so for example, the first 3 bits in the resulting bit stream might represent one integer, then the next 9 bits another integer, etc.
share|improve this answer

Counting set bits, finding lowest/highest set bit, finding nth-from-top/bottom set bit and others can be useful, and it's worth looking at the bit-twiddling hacks site.

That said, this kind of thing isn't day-to-day important. Useful to have a library, but even then the most common uses are indirect (e.g. using a bitset container). Also, ideally, these would be standard library functions - a lot of them are better handled using specialise CPU instructions on some platforms.

share|improve this answer

There's only three that I've ever used with any frequency:

  1. Set a bit: a |= 1 << bit;

  2. Clear a bit: a &= ~(1 << bit);

  3. Test that a bit is set: a & (1 << bit);

share|improve this answer

1) Divide/Multiply by a power of 2

foo >>= x; (divide by power of 2)

foo <<= x; (multiply by power of 2)

2) Swap

x ^= y;
y = x ^ y;
x ^= y;
share|improve this answer
It'd be interesting to see benchmarks demonstrating whether those are actually faster than the normal way on modern compilers. –  sepp2k Oct 7 '09 at 18:04
I'd be pretty confident the shift is faster. The swap is more about not needing additional memory than being faster. –  Taylor Leese Oct 7 '09 at 18:16
@Taylor: Most modern compilers will use a shift when it's the fastest way, without you having to manually code it. –  Ken White Oct 7 '09 at 18:33

While multiplying/dividing by shifting seems nifty, the only thing I needed once in a while was compressing booleans into bits. For that you need bitwise AND/OR, and probably bit shifting/inversion.

share|improve this answer

I wanted a function to round numbers to the next highest power of two, so I visited the Bit Twiddling website that's been brought up several times and came up with this:

i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;

I use it on a size_t type. It probably won't play well on signed types. If you're worried about portability to platforms with different sized types, sprinkle your code with #if SIZE_MAX >= (number) directives in appropriate places.

share|improve this answer

Matters Computational: Ideas, Algorithms, Source Code, by Jorg Arndt (PDF). This book contains tons of stuff, I found it via a link at http://www.hackersdelight.org/

Average without overflow

A routine for the computation of the average (x + y)/2 of two arguments x and y is

static inline ulong average(ulong x, ulong y)
// Return floor( (x+y)/2 )
// Use: x+y == ((x&y)<<1) + (x^y)
// that is: sum == carries + sum_without_carries
    return (x & y) + ((x ^ y) >> 1);
share|improve this answer

I used bitwise operators to efficiently implement distance calculations for bitstrings. In my application bitstrings were used to represent positions in a discretised space (an octree, if you're interested, encoded with Morton ordering). The distance calculations were needed to know whether points on the grid fell within a particular radius.

share|improve this answer

Check out this links. It's for actionscript but bitwise operators are pretty much the same as in other languages: bitwise gems fast integer math

share|improve this answer

Your Answer


