Main Page

Previous Next

Bitwise Operations

As you already know, all these integer variables we have been talking about are represented internally as binary numbers. A value of type int consists of 32 binary digits, known to us computer fans as bits. You can operate on the bit values of integers using the bitwise operators, of which there are four available:

&

AND

|

OR

^

Exclusive OR

~

Complement

Each of these operators works with individual bits as follows:

  • The bitwise AND operator, &, combines corresponding bits in its two operands such that if the first bit AND the second bit are 1, the result is 1 – otherwise the result is 0.

  • The bitwise OR operator, |, combines corresponding bits such that if either one bit OR the other is 1, then the result is 1. Only if both bits are 0 is the result 0.

  • The bitwise exclusive OR (XOR) operator, ^, combines corresponding bits such that if both bits are the same the result is 0, otherwise the result is 1.

  • The complement operator, ~, takes a single operand in which it inverts all the bits, so that each 1 bit becomes 0, and each 0 bit becomes 1.

You can see the effect of these operators in the following examples.

Click To expand

The illustration shows the binary digits that make up the operands and the results. Each of the three binary operations applies to corresponding individual pairs of bits from the operands separately. The complement operator flips the state of each bit in the operand.

Since you are concerned with individual bits with bitwise operations, writing a constant as a normal decimal value is not going to be particularly convenient. A much better way of writing binary values in this case is to express them as hexadecimal numbers, because you can convert from binary to hexadecimal, and vice versa, very quickly. There's more on this in Appendix B.

Converting from binary to hexadecimal is easy. Each group of four binary digits from the right corresponds to one hexadecimal digit. You just work out what the value of each four bits is and write the appropriate hexadecimal digit. For example, the value of a from the illustration is:

Binary

0110

0110

1100

1101

Decimal value

6

6

12

13

Hexadecimal

6

6

C

D

So the value of the variable a in hexadecimal is 0x66CD, where the 0x prefix indicates that this is a hexadecimal value. The variable b in the illustration has the hexadecimal value 0x000F. If you think of the variable b as a mask applied to a, you can view the & operator as keeping bits unchanged where the mask is 1 and setting the rest to 0. Mask is a term used to refer to a particular configuration of bits designed to select out specific bits when it is combined with a variable using a bitwise operator. So if you want to select a particular bit out of an integer variable, just AND it with a mask that has that bit set to 1 and all the others as 0.

You can also look at what the & operator does from another perspective – it forces a bit to 0, if the corresponding mask bit is 0. Similarly, the | operator forces a bit to be 1 when the mask bit is 1.

The & and | operators are the most frequently used, mainly for dealing with variables where the individual bits are used as state indicators of some kind for things that can be either true or false, or on or off. You could use a single bit as a state indicator determining whether something should be displayed, with the bit as 1, or not displayed, with the bit as 0. A single bit can be selected using the & operator – for example, to select the third bit in the int variable indicators, you can write:

thirdBit = indicators & 0x4;     // Select the 3rd bit

We can illustrate how this works if we assume the variable indicators contains the hexadecimal value 0xFF07:

 

Hexadecimal

Binary

   

indicators

0xFF07

1111

1111

0000

0111

mask value

0x4

0000

0000

0000

0100

indicators & 0x4

0x4

0000

0000

0000

0100

All these values should have 32 bits and we are only showing 16 bits here, but you see all you need to know how it works. The mask value sets all the bits in indicators to zero except for the third bit. Here, the result of the expression is non-zero because the third bit in indicators is 1.

On the other hand, if the variable indicators contained the value 0xFF09 the result would be different:

 

Hexadecimal

Binary

   

indicators

0xFF09

1111

1111

0000

1001

mask value

0x4

0000

0000

0000

0100

indicators & 0x4

0x0004

0000

0000

0000

0000

The result of the expression is now zero because the third bit of indicators is zero.

To set a particular bit on, you can use the | operator, so to set the third bit in indicators on, you can write:

indicators = indicators | 0x4;   // Set the 3rd bit on

We can see how this applies to the last value we had for indicators:

 

Hexadecimal

Binary

   

indicators

0xFF09

1111

1111

0000

1001

mask value

0x4

0000

0000

0000

0100

indicators | 0x4

0xFF0D

1111

1111

0000

1101

As you can see, the effect is just to switch the third bit of indicators on. All the others are unchanged. Of course, if the bit were already on, it would stay on.

The bitwise operators can also be used in the op= form. Setting the third bit in the variable indicators is usually written as:

indicators |= 0x4;

Although there is nothing wrong with the original statement we wrote, the one above is just a bit more concise.

To set a bit off you need to use the & operator again, with a mask that has 0 for the bit you want as 0, and 1 for all the others. To set the third bit of indicators off you could write:

indicators &= ~0x4;                 // Set the 3rd bit off

With indicators having the value 0xFF07, this would work as follows:

 

Hexadecimal

Binary

   

indicators

0xFF07

1111

1111

0000

0111

mask value

0x4

0000

0000

0000

0100

~0x4

0xFFFB

1111

1111

1111

1011

indicators & ~0x4

0xFF03

1111

1111

0000

0011

The ^ operator has the slightly surprising ability to interchange two values without moving either value somewhere else. The need for this turns up most frequently in tricky examination questions. If you execute the three statements:

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

the values of a and b will be interchanged, but remember this only works for integers. We can try this out with a couple of arbitrary values for a and b, 0xD00F and 0xABAD respectively – again we will just look at 16 bits for each variable. The first statement will change a to a new value:

a ^= b

Hexadecimal

Binary

   

a

0xD00F

1101

0000

0000

1111

b

0xABAD

1010

1011

1010

1101

a from a^b

0x7BA2

0111

1011

1010

0010

Now the next statement, which calculates a new value of b using the new value of a:

b ^= a

Hexadecimal

Binary

   

a

0x7BA2

0111

1011

1010

0010

b

0xABAD

1010

1011

1010

1101

b from b^a

0xD00F

1101

0000

0000

1111

So b now has a value that looks remarkably like the value that a started out with. Let's look at the last step, which calculates a new value for a using the new value of b:

a ^= b

Hexadecimal

Binary

  

a

0x7BA2

0111

1011

1010

0010

b

0xD00F

1101

0000

0000

1111

a from a^b

0xABAD

1010

1011

1010

1101

Lo and behold, the value of a is now the original value of b. In the old days when all programmers wore lab coats, when computers were driven by steam, and when memory was measured in bytes rather than megabytes, this mechanism could be quite useful since you could interchange two values in memory without having to have extra memory locations available. So if antique computers are your things, this may turn out to be a valuable technique. In fact it's more useful than that. When we get to do some graphics programming you will see that this is very relevant.

Don't forget – all of these bitwise operators can only be applied to integers. They don't work with any other type of value. As with the arithmetic expressions, the bitwise operations are carried out with 32 bits for integers of type short and of type byte, so a cast to the appropriate type is necessary for the result of the expression on the right of the assignment operator. One note of caution – special care is needed when initializing variables of type byte and type short with hexadecimal values to avoid being caught out. For example, you might be tempted to initialize a variable of type byte to binary 1111 1111 with the statement:

byte allBitsOne = 0xFF;    // Wrong!! 

In fact this results in a compiler error message. The literal 0xFF is 1111 1111, so what's the beef here? The beef is that 0xFF is not 1111 1111 at all. The literal 0xFF is type int, so it is the binary value 0000 0000 0000 0000 1111 1111. This happens to be equivalent to the decimal value 128, which is outside the range of type byte. The byte value we are looking for, 1111 1111, is equivalent to the decimal value -1 so the correct way to initialize allBitsOne to 1s is to write:

byte allBitsOne = 0xFFFFFFFF;    // Correct – well done!!

Now the compiler will happily chop off the high order bits to produce the result we are looking for.

Shift Operations

Another mechanism that you have for working with integer variables at the bit level is shifting. You can shift the bits in an integer to the right or the left. Shifting binary digits right or left can be envisaged as dividing or multiplying by powers of two. Shifting the binary value of 3, which is 0011, to the left one bit multiplies it by two. It becomes binary 0110, which is decimal 6. Shifting it to the right by one bit divides it by 2. It becomes binary 0001, which is 1.

Java has three shift operators:

<<

Shift left, filling with zeros from the right

>>

Shift right, propagating the sign bit from the left

>>>

Shift right, filling with zeros from the left

The effect of the operators is shown in the following illustration:

Click To expand

Of course, if the high order bit in the >> operation in the illustration was zero, there would be three zeros at the leftmost end of the result.

Shift operations are often used in combination with the other bitwise operators we have discussed to extract parts of an integer value. In many operating systems a single 32-bit value is sometimes used to store multiple values – two 16-bit values, for instance, that might be screen coordinates. This is illustrated opposite.

Click To expand

This shows how the shift operations can be used to extract either the left or the right 16 bits from the variable value. You can see here why you have an extra shift right operation that propagates the leftmost bit. It is related to the notion of a shift as multiplying or dividing by a power of 2, and the implications of that in the context of negative integers represented in 2's complement form (see Appendix B).

Previous Next
JavaScript Editor Java Tutorials Free JavaScript Editor