Bitwise Operators and Two’s Complement.

(Updated August 5, 2024)

Table of Contents

Bitwise Operators
Two’s Complement Numbers
Shifting and Rotating
Showing the Bits

Bitwise Operators

Within computer science, there is a desire to manipulate individual bits. Although memory is plentiful in many computing systems, that does not excuse one from considering all possible solutions to making a program or system run faster or leaner. Just because you have oodles of memory does not necessarily mean you should use all you like.

Of course, before you can think about storing large amounts of knowledge in small places, you must understand how to store and retrieve such information.

There are only a few operations that can be performed on individual bits: and, or and exclusive-or. The table of bit values and the applied operators is shown below:

Table 1: Bitwise operator results for each bit combination and each operator.

Each bitwise operator is a binary operator and requires two operands. As you can see from the table, the only time the result of & is a 1 is when both operands are 1. Inversely, the only time the result of | is 0 is when both are 0. The ^ operator is only 1 when operands are different, never when they are the same.

To apply this to a group of bits, we would simply line them up like so:

            10011010          10011010          10011010
          & 00111101        | 00111101        ^ 00111101
            --------          --------          --------
            00011000          10111111          10100111

For each grouping of bits, simply perform the operator on each vertical pair of bits in succession. The result of each operation is shown below the hashed line.

Two’s Complement Numbers

The concept of two’s complement is a means of representing meaningful signed and unsigned numbers so that they can be added together by simple digital logic circuits.

In a two’s complement system, we apply a process to invert the sign of a number. This is more easily seen when looking at the binary representation of a base 10 number. Consider the following:

             3 = 00000011
             2 = 00000010
             1 = 00000001
             0 = 00000000
            -1 = 11111111
            -2 = 11111110
            -3 = 11111101
            -4 = 11111100
                 ...
          -127 = 10000001
          -128 = 10000000
           127 = 01111111
           126 = 01111110

Looking closely, you can see that the numbers overflow at -1 when we subtract 1 from 0. Further subtractions show the correct correlation of the number to the bit pattern. We continue to lose 1’s in favor of 0’s. This will continue until we reach -128, where the number overflows again, and the number becomes positive. Hence, we call the leftmost (most significant) bit the sign bit.

To quickly get the negation of a given number, you can simply flip or invert all of the bits and then add 1. Deriving the positive representation of a given value in twos-complement is reasonably straightforward. The negative version takes some practice unless you know the abovementioned process.

Consider the following example to get -59 from 59:

          59   =   00111011

          Flip     11000100
          Add 1 +  00000001
                   --------
                   11000101   =  -59

Just to make sure this is correct, we will take 59 and negate it, producing the positive value again:

          -59   =  11000101

          Flip     00111010
          Add 1 +  00000001
                   --------
                   00111011  =  59

Well, that was pretty simple to prove the mechanism works. But does the math work? In base 10, we know it works because adding a number to its inverse is always zero:

          59                    59
         -59      or        + (-59)
        ----                  -----
           0                     0

But what about in binary? Let us give it a whirl:

          Carry --->    1   1111111
                            00111011 = 59
                          + 11000101 = -59
                            --------
                        1   00000000

Note that the same mechanics of addition are used to sum binary numbers. The only catch is to realize that 1₂ + 1₂ = 10₂. Which is why we have displayed the carry along the top. This shows the complete mechanical process of addition. The resulting 9th bit of carry is simply ignored since an 8-bit quantity plus an 8-bit quantity must yield an 8-bit quantity.

Shifting and Rotating

Bit shifting and rotating are also useful. There are three operators, but not all programming languages support them. These are as follows:

          <<  Arithmetic shift left
          >>  Arithmetic shift right
          >>> Unsigned rotate right  (Note C does not have this operator, it is usually found in Java.)

The arithmetic shift (often called signed shift) keeps the state of the sign bit (the leftmost bit) intact when shifting right and fills in with zeros when shifting left. The rotate right operator always fills with zeros from the left. This is often necessary when the sign is not significant, or a bit needs to be positioned for a particular operation.

Using the >>> operator, we will shift 59₁₀ three bits:

If you look closely, this is effectively divided by 2 for each rotation. So three rotations yield:

(00111011)   59 / 2 = 29 = 00011101
             29 / 2 = 14 = 00001110
             14 / 2 = 7  = 00000111

Using the >> operator on 59₁₀ would yield the same result since it is a positive number, but let us try it with -59_10:

Or another way to look at it:

(11000101)   -59 / 2 = -29 = 11100010
             -29 / 2 = -14 = 11110001
             -14 / 2 = -7  = 11111000

So what happens in the other direction? Well, let us give it a go:

Note that we lost the sign here! Shifting to the left is effectively multiplying by 2 for each bit:

(11000101)   -59 * 2 = -118 = 10001010
            -118 * 2 =   20 = 00010100
              20 * 2 =   40 = 00101000

Remember that this makes sense when you consider that the sign is lost on the second shift due to overflow in the 8-bit space, and therefore the number becomes positive. Remember how two’s complement numbers work, and this will make sense to you.

Showing the Bits

In keeping with the Java premise of “a method for every type,” the example below shows overloaded methods for each data type. The compiler will deduce the correct version based on the type provided in the argument list.

Note that the statement

      System.out.print((i & mask) == 0 ? 0 : 1);

is equivalent to

      if ( (i & mask) == 0)
        System.out.print(0);
      else 
        System.out.print(1);

import java.util.Scanner;

public class Bits3 {
  
  static Scanner kb = new Scanner(System.in);
  
  public static void bitDump(byte i) {
    byte mask = (byte)0x80;
    
    for (int x = 0; x < 8; x++) {
      System.out.print((i & mask) == 0 ? 0 : 1);
      
      mask = (byte)((mask & 0xff) >>> 1);
    }
    System.out.println("");
  }
  
  public static void bitDump(short i) {
    short mask = (short)0x8000;
    
    for (int x = 0; x < 16; x++) {
      System.out.print((i & mask) == 0 ? 0 : 1);
      if ((x+1) % 8 == 0 && x < 15)
        System.out.print("_");
      
      mask = (short)((mask & 0xffff) >>> 1);
    }
    System.out.println("");
  }
  
  public static void bitDump(int i) {
    int mask = 0x8000_0000;
    
    for (int x = 0; x < 32; x++) {
      System.out.print((i & mask) == 0 ? 0 : 1);
      if ((x+1) % 8 == 0 && x < 31)
        System.out.print("_");
      
      mask = mask >>> 1;
    }
    System.out.println("");
  }
  
  public static void bitDump(long i) {
    long mask = 0x8000_0000_0000_0000l;
  
    for (int x = 0; x < 64; x++) {
      System.out.print((i & mask) == 0 ? 0 : 1);
      if ((x+1) % 8 == 0 && x < 63)
        System.out.print("_");
      
      mask = mask >>> 1;
    }
    System.out.println("");
  }
    
  public static void main(String[] args) {

    bitDump((byte)-3);
    bitDump((byte)3);
    bitDump((short)-3);
    bitDump((short)3);
    bitDump(-3);
    bitDump(3);
    bitDump((long)-3);
    bitDump((long)3);
  }
}

Overloaded methods to display the bit patterns of two’s complement numbers.

The code from above will display the following output:

11111101
00000011
11111111_11111101
00000000_00000011
11111111_11111111_11111111_11111101
00000000_00000000_00000000_00000011
11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111101
00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000011

Another version of this is in C. This version is more concise as C does not have function overloading (yes, we know about _Generic, but that’s a hot mess). Instead, we have introduced an additional argument to state the number of significant bits to be printed. The auto-widening of the data will sign-extend the long long.

The switch statement uses an intentional fall-through (no break statements) model to rotate the long long mask down to the needed size for the data type. So, a byte (8 bits) ends up being rotated 56 bits, an int (32 bits) rotates 32 bits, and a long long rotates none since we started with a suitable mask for that size.

#include <stdio.h>

void bitDump(long long i, int bits) {

  unsigned long long mask = 0x8000000000000000ll;
  
  switch (bits) {
    case 8:
      mask >>= 8;
    case 16:
      mask >>= 16;
    case 32:
      mask >>= 32;
    case 64:
      break;
    default:
      printf("Bits must be one of 8, 16, 32 or 64.\n");
      break;
  }

  for (int x = 0; x < bits; x++) {
    printf("%c", (i & mask) == 0 ? '0' : '1');
    if ((x+1) % 8 == 0 && x < bits - 1)
      printf("_");
    
    mask = mask >> 1;
  }
  printf("\n");
}

int main(int argc, char *argv[]) {

  bitDump(-3,8);
  bitDump(3,8);
  bitDump(-3,16);
  bitDump(3,16);
  bitDump(-3,32);
  bitDump(3,32);
  bitDump(-3,64);
  bitDump(3,64);
}