Bitwise Operation and Usage

Real world use cases of bitwise operators

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

Bitwise operation and usage

Bitwise operators are operators that work on multi-bit values, but conceptually one bit at a time.

• AND is 1 only if both of its inputs are 1, otherwise it's 0.
• OR is 1 if one or both of its inputs are 1, otherwise it's 0.
• XOR is 1 only if exactly one of its inputs are 1, otherwise it's 0.
• NOT is 1 only if its input is 0, otherwise it's 0.

These can often be best shown as truth tables. Input possibilities are on the top and left, the resultant bit is one of the four (two in the case of NOT since it only has one input) values shown at the intersection of the inputs.

AND | 0 1     OR | 0 1     XOR | 0 1    NOT | 0 1
----+-----    ---+----     ----+----    ----+----
 0  | 0 0      0 | 0 1       0 | 0 1        | 1 0
 1  | 0 1      1 | 1 1       1 | 1 0

One example is if you only want the lower 4 bits of an integer, you AND it with 15 (binary 1111) so:

    201: 1100 1001
AND  15: 0000 1111
------------------
 IS   9  0000 1001

The zero bits in 15 in that case effectively act as a filter, forcing the bits in the result to be zero as well.

In addition, >> and << are often included as bitwise operators, and they "shift" a value respectively right and left by a certain number of bits, throwing away bits that roll of the end you're shifting towards, and feeding in zero bits at the other end.

So, for example:

1001 0101 >> 2 gives 0010 0101
1111 1111 << 4 gives 1111 0000

Note that the left shift in Python is unusual in that it's not using a fixed width where bits are discarded - while many languages use a fixed width based on the data type, Python simply expands the width to cater for extra bits. In order to get the discarding behaviour in Python, you can follow a left shift with a bitwise and such as in an 8-bit value shifting left four bits:

bits8 = (bits8 << 4) & 255

With that in mind, another example of bitwise operators is if you have two 4-bit values that you want to pack into an 8-bit one, you can use all three of your operators (left-shift, and and or):

packed_val = ((val1 & 15) << 4) | (val2 & 15)

• The & 15 operation will make sure that both values only have the lower 4 bits.
• The << 4 is a 4-bit shift left to move val1 into the top 4 bits of an 8-bit value.
• The | simply combines these two together.

If val1 is 7 and val2 is 4:

                val1            val2
                ====            ====
 & 15 (and)   xxxx-0111       xxxx-0100  & 15
 << 4 (left)  0111-0000           |
                  |               |
                  +-------+-------+
                          |
| (or)                0111-0100

When to use the bitwise and operator (&)?

As the comments mentioned, num&1 is a bitwise AND between num and 1.

Since 1 in binary is ...000000001, the AND will result True iff the least significant bit of num is 1, in other words, if it is odd (here some explanation of binary)

What are bits and bitwise operations used for?

You can pack data in a very concise format.

The smallest amount that an x86 computer can adress is a byte - that's 8 bits.

If your application has a 24 yes/no flags (bools), would you store them in 1 byte each? That's 24 bytes of data. If you use bits, then each byte contains 8 of those bools - so you only need 3 bytes for 24 yes/no values:

> 1 Byte per flag:
> 0000 0000 = off
> 0000 0001 = on
> Easy to check: if(b == 0) { /* flag is off */ } else if(b == 1) { /* flag is on */ }

> 1 Bit per flag
> 0011 1101 = Flags 1, 4, 8, 16 and 32 are on, flags 2, 64 and 128 are off
> Packs 8 flags in 1 byte
> Harder to check:
> if( (b & 32) != 0) { /* Flag 32 is on */ }

This is important for network protocols and other systems where every byte really counts.

For general purpose business applications, there is usually no need for the additional complexity, just use 1 byte per flag.

This isn't just used for bools. For example, some applications may want to store two numbers than can go from 0-15 - an example is the Commodore 64 which really needed to conserve RAM wherever possible. One byte can hold two of those numbers:

> Instead of interpreting this as 8 bits (ranging from 1 to 128)
> this is really two 4 bit numbers:
> 1001 0110
> First Number: 1001 = 1 + 8 = 9
> Second Number: 0110 = 2 + 4 = 6
>
> Getting the first number requires a bit shift to move them into position:
> (b >> 4) turns the above number into this:
> 0000 1001 - this can now be simply cast as a byte and returns 9
>
> The second number requires us to "turn off" the first 4 bits
> We use the AND operator for this: b = (b & 15)
> 15 in decimal is 0000 1111 in binary.
>
> 1001 0110 AND
> 0000 1111 =
> 0000 0110
>
> Once again, the result can be interpreted as a byte and results in the number 6

One more really neat trick is to quickly check if a number is even or odd. An odd number always has the lowest significant bit (the 1 Bit) set, while an even numer always as it clear.

So your check for IsEven looks like this:

return (b & 1) == 0; // Bit 1 not set - number is even

(Note: Depending on the language, Compilers MAY decide to optimize stuff, but in a nutshell, that's it)

practical applications of bitwise operations

Although everyone seems to be hooked on the flags usecase, that isn't the only application of bitwise operators (although probably the most common). Also C# is a high enough level language that other techniques will probably be rarely used, but it's still worth knowing them. Here's what I can think of:

---

The << and >> operators can quickly multiply by a power of 2. Of course, the .NET JIT optimizer will probably do this for you (and any decent compiler of another language as well), but if you're really fretting over every microsecond, you just might write this to be sure.

Another common use for these operators is to stuff two 16-bit integers into one 32-bit integer. Like:

int Result = (shortIntA << 16 ) | shortIntB;

This is common for direct interfacing with Win32 functions, which sometimes use this trick for legacy reasons.

And, of course, these operators are useful when you want to confuse the inexperienced, like when providing an answer to a homework question. :)

In any real code though you'll be far better off by using multiplication instead, because it's got a much better readability and the JIT optimizes it to shl and shr instructions anyway so there is no performance penalty.

---

Quite a few curious tricks deal with the ^ operator (XOR). This is actually a very powerful operator, because of the following properties:

• A^B == B^A
• A^B^A == B
• If you know A^B then it's impossible to tell what A and B are, but if you know one of them, you can calculate the other.
• The operator doesn't suffer from any overflows like multiplication/division/addition/subtraction.

A couple of tricks I have seen using this operator:

Swapping two integer variables without an intermediary variable:

A = A^B // A is now XOR of A and B
B = A^B // B is now the original A
A = A^B // A is now the original B

Doubly-linked list with just one extra variable per item. This will have little use in C#, but it might come in handy for low level programming of embedded systems where every byte counts.

The idea is that you keep track of the pointer for the first item; the pointer for the last item; and for every item you keep track of pointer_to_previous ^ pointer_to_next. This way you can traverse the list from either end, yet the overhead is just half that of a traditional linked list. Here's the C++ code for traversing:

ItemStruct *CurrentItem = FirstItem, *PreviousItem=NULL;
while (  CurrentItem != NULL )
{
    // Work with CurrentItem->Data

    ItemStruct *NextItem = CurrentItem->XorPointers ^ PreviousItem;
    PreviousItem = CurrentItem;
    CurrentItem = NextItem;
}

To traverse from the end you just need to change the very first line from FirstItem to LastItem. That's another memory saving right there.

Another place where I use the ^ operator on a regular basis in C# is when I have to calculate a HashCode for my type which is a composite type. Like:

class Person
{
    string FirstName;
    string LastName;
    int Age;

    public int override GetHashCode()
    {
        return (FirstName == null ? 0 : FirstName.GetHashCode()) ^
            (LastName == null ? 0 : LastName.GetHashCode()) ^
            Age.GetHashCode();
    }
}

When should I use a bitwise operator?

Bitwise | and & and logical || and && are totally different.

Bitwise operators perform operations on the bits of two numbers and return the result. That means it's not a yes or no thing. If they're being used in conditional statements, they're often used as part of logical comparisons. For example:

if ($x & 2 == 2) {
    // The 2^1 bit is set in the number $x
}

Logical operators compare two (or more) conditions/expressions and return true or false. You use them most commonly in conditional statements, like if and while. For example:

if ($either_this || $or_this) {
    // Either expression was true
}

When to use Bitwise Operators during webdevelopment?

My main use for bitwise operators could be relevant anywhere - representing a set of flags. For instance, you might have an integer in the database representing a set of security permissions for a user, and in your web app you would have to check those before continuing.

Those tend to only require & and | - e.g.

if ((permissions & Permission.CreateUser) != 0)
{
    ...
}

or

Permission requiredPermission = Permission.CreateUser
                                | Permission.ChangePassword;

Bit shifting operators are less useful in "business" applications in my experience.

Bitwise or operator | usage in C for aligning memory blocks

A standard way to make a number divisible by 8 is:

len = (len + 7) & 0xfffffff8; /* for positive 32-bit values */

That should be easier to understand than your friend's construct (which BTW probably works as well, but see below).

The construct you have sets the lower 3 bits of your number by bitwise ORing it with 7 (thus creates a number that has a remainder of 7 when divided by 8), then adds 1 to make it divisible by 8. What the -1 means, you should work out on your own. I wouldn't even look at it nor use it if you don't anderstand what it does at first glance.

Whether it is advisable to use signed integers as addresses and block lengths you will surely get some other comments.

How to use bitwise operations to assign specific bits of a byte according to two other bytes? (bit blend according to a mask)

The standard bithack for this is "Merge bits from two values according to a mask" - I added your variable names for the inputs to the existing comments from Sean Anderson's collection of bithacks.

unsigned int a;    // (ByteToAlter)    value to merge in non-masked bits
unsigned int b;    // (ValuesToAssign) value to merge in masked bits
unsigned int mask; // (BitsToAssign)   1 where bits from b should be selected; 0 where from a.

unsigned int r;    // result of (a & ~mask) | (b & mask) goes here

r = a ^ ((a ^ b) & mask); 

As the bithack comments note, the straight-forward way is (a & ~mask) | (b & mask) - clear the bits you're not keeping in each input, then OR them together.

How a ^ ((a ^ b) & mask) works:

bitdiff = a^b is the bitwise difference between those inputs.

It has a 1 where they differ, and a 0 where they're the same. (By definition of XOR).

a ^ bitdiff would flip every bit in a that's different from b. In fact, b == a ^ bitdiff.

One way to show that's true is that XOR is associative, so a ^ (a^b) = (a ^ a) ^ b.

And x^x = 0, just like x-x = 0.

0 ^ x = x, so (a^a) ^ b = 0 ^ b = b.

But if we mask the bitdiff to only set bits of a to bits from b at certain positions, we've achieved our goal: bitwise blend according to a mask. blend = a ^ (bitdiff & mask);

---

Special cases of the (a & ~mask) | (b & mask) simple version

If your inputs are arranged so ValuesToAssign only has any 1 bits at positions selected by the mask, you can optimize away the b & mask part, leaving just (a & ~mask) | b. (Eraklon's answer). Clear the unselected bits, then OR in the new values to set any bits that should be set.

A further special case is when ValuesToAssign == BitsToAssign, i.e. the modification only ever sets bits, never clearing them. That's what OR does, so of course this case optimizes to a | b, with no need to clear bits in a before ORing.

---

Efficiency:

r = a ^ ((a ^ b) & mask); is only 3 boolean operations,

vs. 4 for (a & ~mask) | (b & mask) if all three inputs are runtime-variables. (One bitwise NOT, two AND, plus an OR).

If mask is a constant, then constant-propagation into ~mask makes it a constant, and most machines can do AND-immediate with at least an 8-bit AND mask. So you'd still only need 3 instruction: two ANDs (with inverse constants) and an OR.

Some machines (like x86 with BMI1) even have an andn instruction that does x & ~y, allowing the (a & ~mask) | (b & mask) to be done with 3 instructions.

For latency, (a & ~mask) | (b & mask) has more instruction-level parallelism. If mask and ~mask are ready ahead of a and b, there are only two parallel AND operations, and an OR, from a and b inputs being ready to the output being ready. On a normal superscalar machine (that can do two independent AND ops in the same cycle), that's only 2 cycle latency from inputs to outputs. (Again, assuming mask is ready early, or that an instruction like andn exists to do a & ~mask in a single operation).

If the critical path goes through mask (i.e. it's not ready early), and you don't have an instruction like andn to do ~ and & as one operation, the latency from mask to result is 3 operations, ~, &, and |. (Assuming the b & mask can run in parallel without slowing down any of those three).

Latencies for (a & ~mask) | (b & mask) on a modern OoO exec machine.

(Not the same thing as throughput cost)

• a -> result: 2 cycles
• b -> result: 2 cycles
• mask -> result: 3 cycles (or 2 on some machines)

But the bit-difference way doesn't have any ILP; it's a chain of 3 operations. a^b requires both of those inputs to be ready for the first step, then mask needs to be ready for the & mask step. The final a ^ ... step is using inputs that were already needed earlier. So it's only 3 operations, but they're serial.

Latencies for a ^ ((a ^ b) & mask) on a modern OoO exec machine.

• a -> result: 3 cycles
• b -> result: 3 cycles
• mask -> result: 2 cycles

Related Q&As:

• Merge bit sequences a and b according to a mask - this is called a blend in SIMD programming. IDK if anyone else uses the "bit-blend" term I like to use for this operation, but IMO that clearly describes it. x86's AVX-512 extension has a 3-input boolean operation vpternlog with a truth-table from an 8-bit immediate, and thus can do it in a single instruction.

• Swapping bits at a given point between two bytes - The same bithack idea, but applying the masked bit-difference to both inputs to exchange bits at the mask positions.

• https://catonmat.net/low-level-bit-hacks - starts gently with an intro to the operators (like ^ being bitwise XOR). Includes bithacks that use + and - (and the carry propagation effects of hitting a 1 or 0, like x & (x-1) to clear the right-most set bit.)

• https://agner.org/optimize/ for more about tuning for modern CPUs.

---

Related Topics