Ummm, not much to say really...

All numbers are stored as a binary code, i.e. in base 2.

If you bitwise OR two bits then the result is set iff either of the two input bits were set.

If you bitwise AND two bits then the result is set iff both of the input bits were set.

If you bitwise EXCLUSIVE-OR two bits then the result is set iff exactly one of the input bits was set.

The bitwise NOT of a single bit is that bit inverted.

The effect of carrying out a bitwise operation using integers is that the bitwise operation is carried out on each digit separately.

The C operators are '|' for OR, '&' for AND, '^' for EXCLUSIVE-OR and '~' for NOT. |, & and ^ are binary operators, ~ is a unary operator.

Bitwise operations are often seen in C/C++ programs to represent flags. For example:

Another common construction is this:

if(NewVar^OldVar&NewVar&FLAG_1)
{
   // executes only if flag 1 is set in NewVar but not in OldVar
}
OldVar = NewVar;

Which is fairly easy to understand. The EXCLUSIVE OR effectively produces a number with a bit set everywhere a bit has changed between OldVar and NewVar, the AND with NewVar keeps only those bits that have changed and are set in NewVar, and the AND with FLAG_1 throws away all those bits that aren't flag 1. Then the usual C rule of 'execute if expression is non-zero' takes the code into the if statement.

Ummm, I guess you also sometimes see:

a ^= b;
b ^= a;
a ^= b;

To do an in-place swap of the values of a and b. That works because binary operators are commutative and associative - b ^ a ^ b = a ^ b ^ b = a ^ (b ^ b) = a ^ 0 = a. And in that case we go from:

• a = a, b = b; to

• a = a^b, b = b; to

• a = a^b, b = b^a^b; to

• a = a^b^b^a^b, b = b^a^b

So at the end, a = a^b^b^a^b = (a^a) ^ (b^b) ^ b = 0 ^ 0 ^ b = b, and b = b ^ a ^ b = b ^ b ^ a = 0 ^ a = a.

It's rare that you need to do bitwise stuff other than to communicate with hardware at the lowest level, but lots of programmers with lower level experience put a lot of it around because it just matches how they think about things.

Probably lots more to say, but with these things it's all just directly consequential from the definition...

EDIT: P.s. neat idea, especially if someone is going to start transposing this stuff into the wiki?

I use bitwise operators a lot to check/set/clear bit-encoded flags, as TH stated. I tend to use hexadecimal notation rather than decimal when defining flags, mainly because it's more closely linked to the lower level bitwise encoding.

My main source of frustration is trying to use bit flags in FORTRAN. Let's just say it wasn't designed with bitwise operators in mind; it uses functions to provide similar functionality: BTEST, DSHIFTL, DSHIFTR, IAND, IBCHNG, IBCLR, IBITS, IBSET, IEOR, IOR, ISHA, ISHC, ISHFT, ISHFTC, ISHL, IXOR, LSHIFT, NOT, RSHIFT , SHIFTL, SHIFTR.
I often find myself wishing for the simplicity of bitwise operators in FORTRAN... they make the code look so much more compact and easier to follow.

enum Flags1
{
    flag1 = 001,
    flag2 = 002,
    flag3 = 004,
    flag4 = 010,
    flag5 = 020
};

Fixed.

nvm, need more sleep.

Only if you know MYFLAG is set.
The proper way would be flags &= ~MYFLAG.

To flip specific bits of a number , Bitwise XOR the number with a number that has only the bits you want to flip set to 1.

//
const int X = 1;
const int Y = 2;
const int Z = 4;

int a = X | Z;
int b = a ^ Y;
int c = X | Y | Z;
if (c == b) {XOR_1_Flips_Bits();}
//

1 XOR 0 is 1 because they are different
0 XOR 0 is 0 because they are the same
So if you XOR a bit with 0 it remains the same.

0 XOR 1 is 1 because they are different
1 XOR 1 is 0 because they are the same
So if you XOR a bit with 1 it is flipped.

I made a mistake in the code I posted - I used binary NOT (~) instead of XOR (^), and I compared a to c when I meant to compare b to c. It is corrected now.

On a different note, I thought XOR variable swapping was so cool when I first saw it, but it performs much more slowly than using temporary variables to swap the values.

TestIntSwapSpeed.cpp

Profiling results :

Unoptimized

mingw32-g++ -Wall -pg -o TestIntSwapSpeed.exe TestIntSwapSpeed.cpp

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 31.05      3.94     3.94 500000000     0.00     0.00  IntXorSwap(int&, int&)
 24.27      7.02     3.08 500000000     0.00     0.00  IntTempSwap(int&, int&)
 22.62      9.89     2.87        1     2.87     5.95  TestTempSwap(int, int, unsigned int)
 22.06     12.69     2.80        1     2.80     6.74  TestXorSwap(int, int, unsigned int)

Optimized with -O2

mingw32-g++ -Wall -pg -O2 -o TestIntSwapSpeed.exe TestIntSwapSpeed.cpp

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 49.13      3.10     3.10 500000000     0.00     0.00  IntXorSwap(int&, int&)
 27.42      4.83     1.73 500000000     0.00     0.00  IntTempSwap(int&, int&)
 11.89      5.58     0.75        1     0.75     2.48  TestTempSwap(int, int, unsigned int)
 11.57      6.31     0.73        1     0.73     3.83  TestXorSwap(int, int, unsigned int)

So unoptimized, 500,000,000 swaps using XOR took 3.94 seconds and using a temp variable took 3.08 seconds.
Optimized, 500,000,000 swaps using XOR took 3.10 seconds and using a temp variable took 1.73 seconds.

Percentage wise, unoptimized XOR swapping takes ~128% as much time as temp swapping, and optimized XOR swapping takes 180% as much time as temp swapping for integers.

Here's the assembly code MinGW produces when there's no profiling :

Unoptimized :

mingw32-g++ -Wall -S -o TestIntSwapSpeed_asm.txt TestIntSwapSpeed.cpp

Optimized :

mingw32-g++ -Wall -O2 -S -o TestIntSwapSpeed_O2_asm.txt TestIntSwapSpeed.cpp

Assembly operation tallies :

Version                           pushl  popl  movl  xorl  subl leave   total
-----------------------------------------------------------------------------------
Unoptimized
XOR swap  (__Z10IntXorSwapRiS_)       1     1    16     3     0     0      21
Temp swap (__Z11IntTempSwapRiS_)      1     0    11     0     1     1      14     

Optimized
XOR swap  (__Z10IntXorSwapRiS_)       1     1     6     3     0     0      11
Temp swap (__Z11IntTempSwapRiS_)      2     2     7     0     0     0      11

The xorl operation must be pretty slow if both optimized versions take the same number of operations but the XOR swap takes 9/5 as long to complete.

You're right. The XOR method will be even slower then.

Unoptimized :

mingw32-g++ -Wall -pg -o TestIntSwapSpeed.exe TestIntSwapSpeed.cpp

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 34.43      4.61     4.61 500000000     0.00     0.00  IntXorSwap(int&, int&)
 23.30      7.73     3.12 500000000     0.00     0.00  IntTempSwap(int&, int&)
 22.03     10.68     2.95        1     2.95     7.56  TestXorSwap(int, int, unsigned int)
 20.24     13.39     2.71        1     2.71     5.83  TestTempSwap(int, int, unsigned int)

Optimized with -O2

mingw32-g++ -Wall -O2 -pg -o TestIntSwapSpeed.exe TestIntSwapSpeed.cpp

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 53.09      2.92     2.92 500000000     0.00     0.00  IntXorSwap(int&, int&)
 26.18      4.36     1.44 500000000     0.00     0.00  IntTempSwap(int&, int&)
 13.45      5.10     0.74        1     0.74     2.18  TestTempSwap(int, int, unsigned int)
  7.27      5.50     0.40        1     0.40     3.32  TestXorSwap(int, int, unsigned int)

Execution time ratio for updated XOR method to temp method :
Unoptimized : ~148%
Optimized : ~203%

Assembly output
(unoptimized and optimized versions of _Z10IntXorSwapRiS together)

Tallies :

Version                           pushl  popl  cmpl  movl  xorl    je   total
-----------------------------------------------------------------------------------
Unoptimized
XOR swap  (__Z10IntXorSwapRiS_)       1     1     1    17     3     1      24
Optimized
XOR swap  (__Z10IntXorSwapRiS_)       1     1     1     6     3     1      13

It's interesting to see that the -O2 version was able to trim off 11 movl operations. Is that the difference between keeping the data in the registers and checking it from memory?

How about "a^=a" versus "a=0"? Is the former still faster? I can't imagine it is.

A preference for obfuscated code? Hmm...

I didn't know! Do you have a link where this is discussed in a bit more detail?

I like xor-swap because it's easy to implement as a CPP macro--no passing pointers to a function and no temp variable. The only place I've ever used bitshifts and bitwise things like that is in a very simplistic implementation of ARC4; I'm not doing things like that much anymore.

If you create a function, there are no temp variables (that you see or care about). I personally always use the std functions wherever possible:

int a = 1;
int b = 2;

std::swap (a, b);

How does that std::swap work? It shouldn't be able to swap variables in the calling context without getting pointers to them, unless C++ is much weirder than I thought.