Bitwise Operators in C

Introduction

When you learn to program in a high-level language like C (although C is fairly low-level, as
high-level languages go), the idea is to avoid worrying too much about the hardware. You want
the ability to represent mathematical abstractions, such as sets, etc. and have high level language
features like threads, higher-order functions, exceptions.

High-level languages, for the most part, try to make you as unaware of the hardware as possible.
Clearly, this isn't entirely true, because efficiency is still a major consideration for some
programming languages.

C, in particular, was created to make it easier to write operating systems. Rather than write
UNIX in assembly, which is slow process (because assembly code is tedious to write), and not
very portable (because assembly is specific to an ISA), the goal was to have a language that
provided good control-flow, some abstractions (structures, function calls), and could be
efficiently compiled and run quickly.

Writing operating systems requires the manipulation of data at addresses, and this requires
manipulating individual bits or groups of bits.

That's where two sets of operators are useful: bitwise operators and bitshift operators.

You can find these operators in C, C++, and Java (and presumably C#, since it's basically Java).
Bitwise operators allow you to read and manipulate bits in variables of certain types.

Even though such features are available in C, they aren't often taught in an introductory level
programming course. That's because intro level courses prefer to emphasize abstraction. With
many departments using Java, there's a trend to increase what's abstract, and not get into the
representation.

For example, some languages have support for stacks, queues, hashtables, and so forth. These
"canned" data structures are meant to provide you, the programmer, with objects that perform
certain tasks, while relieving you of the tedium and detail of understanding how the data is
represented.

Nevertheless, if you intend to do some work in systems programming, or other forms of low-
level coding (operating systems, device drivers, socket programming, network programming),
knowing how to access and manipulate bits is important.

Generic Bitwise Operations

Bitwise operators only work on a limited number of types: int and char. This seems restrictive--
and it is restrictive, but it turns out we can gain some flexibility by doing some C "tricks".
It turns out there's more than one kind of int. In particular, there's unsigned int, there's short int,
there's long int, and then unsigned versions of those ints.

The "C" language does not specify the difference between a short int, an int and a long int,
except to state that:

sizeof( short int ) <= sizeof( int ) <= sizeof( long )

You will find that these sizes vary from ISA to ISA, and possibly even compiler to compiler. The
sizes do not have to be distinct. That means all three sizes could be the same, or two of three
could be the same, provided that the above restrictions are held.

Bitwise operators fall into two categories: binary bitwise operators and unary bitwise operators.
Binary operators take two arguments, while unary operators only take one.

We're going to discuss binary operators first, and we'll do in the context of a fake binary operator
called @. Thus, we write x @ y to perform bitwise @ on x and y.

Bitwise operators, like arithmetic operators, do not change the value of the arguments. Instead, a
temporary value is created. This can then be assigned to a variable. For example, when you write
x + y, neither x nor y have their value changed.

Let's assume that we are doing bitwise @ on two unsigned int variables. Let's assume that
unsigned ints use 32 bits of memory. We define two variables X and Y where

X = x31x30....x0
Y = y31y30....y0
We want to be able to refer to each bit of X and Y, which we do so by writing out the bits by
writing the variable name in lowercase and adding the appropriate subscript for thie bit number.

The subscripts follow the convention we've used so far. The least significant bit has a subscript
of 0, and is the rightmost bit. The most significant bit has a subscript of N-1 (for N bits), and is
the leftmost bit. In this case N = 32 so the MSb has a subscript of 31.

Let's define @1 to be the @ operation performed on two individual bits. @ is performed on all 32
bits simultaneously.

Furthermore, let's call the temporary value created, T. Normally, this temporary value does not
have a name. It is generated while the program is running, and used in other computations. Thus,
when you write c = a + b, a temporary value is created for the sum a + b, and this temporary
value then gets copied into c.

Of course, for efficiency, the temporary value might not be generated, and the value written
directly to c. For more complex statements, such as c = (a + b) - d, temporary values are often
created to store intermediate results. These temporary values are created by the runtime system,
and are not given variable names.
We define Z = X @ Y as:

zi = xi @1 yi, for 0 <= i <= N - 1

In words, to compute the ith bit of Z, you should perform the operation on the ith bit of X and ith
bit of Y.

Bitwise AND

This makes more sense if we apply this to a specific operator. In C/C++/Java, the & operator is
bitwise AND. The following is a chart that defines &1, defining AND on individual bits.
xi yi xi &1 yi
0 0 0
0 1 0
1 0 0
1 1 1

We can do an example of bitwise &. It's easiest to do this on 4 bit numbers, however.

Variable b3 b2 b1 b0
x 1 1 0 0
y 1 0 1 0
z=x&y 1 0 0 0

Bitwise OR

The | operator is bitwise OR (it's a single vertical bar). The following is a chart that defines | 1,
defining OR on individual bits.
xi yi xi |1 yi
0 0 0
0 1 1
1 0 1
1 1 1

We can do an example of bitwise |. It's easiest to do this on 4 bit numbers, however.

Variable b3 b2 b1 b0
x 1 1 0 0
y 1 0 1 0
z=x|y 1 1 1 0

Bitwise XOR

The ^ operator is bitwise XOR. The usual bitwise OR operator is inclusive OR. XOR is true only
if exactly one of the two bits is true. The XOR operation is quite interesting, but we defer talking
about the interesting things you can do with XOR until the next set of notes.

The following is a chart that defines ^1, defining XOR on individual bits.

xi yi xi ^1 yi
0 0 0
0 1 1
1 0 1
1 1 0

We can do an example of bitwise ^. It's easiest to do this on 4 bit numbers, however.

Variable b3 b2 b1 b0
x 1 1 0 0
y 1 0 1 0
z=x^y 0 1 1 0

Bitwise NOT

There's only one unary bitwise operator, and that's bitwise NOT. Bitwise NOT flips all of the
bits.

There's not that much to say about it, other than it's not the same operation as unary minus.

The following is a chart that defines ~1, defining NOT on an individual bit.

xi ~1 xi
0 1
1 0

We can do an example of bitwise ~. It's easiest to do this on 4 bit numbers (although only 2 bits
are necessary to show the concept).
Variable b3 b2 b1 b0
x 1 1 0 0
z = ~x 0 0 1 1

Uses of Bitwise Operations

Occasionally, you may want to implement a large number of Boolean variables, without using a
lot of space.

A 32-bit int can be used to stored 32 Boolean variables. Normally, the minimum size for one
Boolean variable is one byte. All types in C must have sizes that are multiples of bytes.
However, only one bit is necessary to represent a Boolean value.

You can also use bits to represent elements of a (small) set. If a bit is 1, then element i is in the
set, otherwise it's not.

You can use bitwise AND to implement set intersection, bitwise OR to implement set union.

In upcoming notes, you'll learn how to find the value of individual bits of a char or int.

Facts About Bitwise Operators

Consider the expression x + y. Do either x or y get modified? The answer is no.

Most built-in binary operators do not modify the values of the arguments. This applies to logical
operators too. They don't modify their arguments.

There are operators that do assignment such as +=, -=, *=, and so on. They apply to logical
operators too. For example, |=, &=, ^=. Nearly all binary operators have a version with = after it.

Summary

Bitwise operators only work on limited types: int and char (and variations of int). You can, with
some casting, make it work on other types. These operators, in conjunction with bitshift
operators allow you to access and modify bits.

A bitwise operation operates on one or more bit patterns or binary numerals at the level of their
individual bits. This is used directly at the digital hardware level as well as in microcode,
machine code and certain kinds of high level languages. On the simple low cost digital
processors used in many embedded systems, bitwise operations are typically several times as fast
as multiplication, sometimes also significantly faster than addition, at least in certain technical
circumstances. On the other hand, modern processors in high performance segments usually
perform addition and multiplication as fast as bitwise operations[1] but the latter typically occupy
less machine resources and may therefore be more optimal for overall performance and/or power
consumption. Division is normally very slow compared to bitwise operations.

Contents

 1 Bitwise operators
o 1.1 NOT
o 1.2 AND
o 1.3 OR
o 1.4 XOR
 1.4.1 See also
 2 Bit shifts
o 2.1 Arithmetic shift
o 2.2 Logical shift
o 2.3 Rotate no carry
o 2.4 Rotate through carry
o 2.5 Shifts in C, C++, C#
o 2.6 Shifts in Java
o 2.7 Shifts in Pascal
 3 Applications
 4 See also
 5 References
 6 External links

[edit] Bitwise operators

Note that in the explanations below, any indication of a bit's position is being counted from the
right side, advancing left. For example: the 4 bits 0001 (decimal 1) has zeroes at every position
but the first one.

[edit] NOT

The bitwise NOT, or complement, is a unary operation that performs logical negation on each
bit, forming the ones' complement of the given binary value. Digits which were 0 become 1, and
vice versa. For example:

NOT 0111 (decimal 7)

= 1000 (decimal 8)
For two's complement signed integers, the bitwise complement of a number is equal to the
negative of that number minus 1. i.e. NOT x = -x - 1 . For unsigned integers, the bitwise
complement of a number is the "mirror reflection" of the number across the half-way point of the
range of the unsigned integer type. For example, for 8-bit unsigned integers, NOT x = 255 - x,
which can be visualized on a graph, as a downward line, which effectively "flips" an increasing
range from 0 to 255, to a decreasing range from 255 to 0. (One simple but illustrative example
use of this is to invert a grayscale image where each pixel is stored as an unsigned integer.)

[edit] AND

A bitwise AND takes two binary representations of equal length and performs the logical AND
operation on each pair of corresponding bits. For each pair, the result is 1 if the first bit is 1 AND
the second bit is 1; otherwise, the result is 0 in this we perform the multiplication of two bits
i.e..1*0=0 and 1*1=1). For example:

0101 (decimal 5)
AND 0011 (decimal 3)
= 0001 (decimal 1)

This may be used to determine whether a particular bit is 1 or 0. For example, given a bit pattern:
0011 (decimal 3), determining whether the second bit is 1 may be done by using a bitwise AND
with a bit pattern containing 1 only in that bit:

0011 (decimal 3)
AND 0010 (decimal 2)
= 0010 (decimal 2)

Because the result 0010 is non-zero, we know the second bit in the original pattern was 1. This is
often called bit masking. (By analogy, the use of masking tape covers, or masks, portions that
should not be altered or portions that are not of interest. In this case, the 0 values mask the bits
that are not of interest.)

If we store the result, this may also be used to clear selected bits in a register. Given the example:
0110 (decimal 6), the second bit may be cleared (i.e. set to 0) by using a bitwise AND with the
pattern that has a zero only in the selected bit:

0110 (decimal 6)
AND 1101 (decimal 13)
= 0100 (decimal 4)

[edit] OR

A bitwise OR takes two bit patterns of equal length and performs the logical inclusive OR
operation on each pair of corresponding bits. For each pair, the result is 1 if the first bit is 1 OR
the second bit is 1 OR both bits are 1; otherwise, the result is 0 and also we perform addition of
bits i.e(0+1=1..like that). For example:

0101 (decimal 5)
OR 0011 (decimal 3)
= 0111 (decimal 7)

The bitwise OR may be used to set selected bits. One example is to set a specific bit (or flag) in a
register where each bit represents an individual Boolean state. For example: 0010 (decimal 2)
can be considered a set of four flags. The first, third, and fourth flags are clear (0), while second
the flag is set (1). The fourth flag may be set by performing a bitwise OR between this value and
a bit pattern in which the fourth flag is set:

0010 (decimal 2)
OR 1000 (decimal 8)
= 1010 (decimal 10)

This technique is an efficient way to deal with a number of Boolean values using the minimum
of memory.

[edit] XOR

A bitwise exclusive OR takes two bit patterns of equal length and performs the logical XOR
operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is
1 OR only the second bit is 1, but will be 0 if both are 1 or both are 0. This is equivalent to being
1 if the two bits are different, and 0 if they are the same. For example:

0101 (decimal 5)
XOR 0011 (decimal 3)
= 0110 (decimal 6)

Assembly language programmers sometimes use the XOR operation as a short-cut to set the
value of a register to zero. Performing XOR on a value against itself always yields zero, and on
many architectures this operation requires fewer CPU clock cycles and/or fewer bytes (less
precious cache-space) than loading a zero value and saving it to the register.

The bitwise XOR may be used to invert selected bits in a register (also called toggle or flip).
Given the bit pattern: 0010 (decimal 2) the second and forth bits may be toggled simultaneously
by a bitwise XOR with a bit pattern containing 1 in the second and forth positions:

0010 (decimal 2)
XOR 1010 (decimal 10)
= 1000 (decimal 8)

This technique may be used to manipulate bit patterns representing sets of Boolean states.

[edit] See also

 XOR swap algorithm

 XOR linked list
[edit] Bit shifts

The bit shifts are sometimes considered bitwise operations, because they operate on the binary
representation of an integer instead of its numerical value; however, the bit shifts do not operate
on pairs of corresponding bits, and therefore cannot properly be called bit-wise. In these
operations the digits are moved, or shifted, to the left or right. Registers in a computer processor
have a fixed width, so some bits will be "shifted out" of the register at one end, while the same
number of bits are "shifted in" from the other end; the differences between bit shift operators lie
in how they determine the values of the shifted-in bits.

[edit] Arithmetic shift

Main article: Arithmetic shift

Left arithmetic shift

Right arithmetic shift

In an arithmetic shift, the bits that are shifted out of either end are discarded. In a left arithmetic
shift, zeros are shifted in on the right; in a right arithmetic shift, the sign bit is shifted in on the
left, thus preserving the sign of the operand. Further on, while shifting right, the empty spaces
will be filled up with a copy of the most significant bit (MSB). Meaning by shifting the second
arithmetic shift register (ASR#2), with a MSB=1, you fill up with 1.

This example uses an 8-bit register:

00010111 LEFT-SHIFT
= 00101110
00010111 RIGHT-SHIFT
= 00001011
In the first case, the leftmost digit was shifted past the end of the register, and a new 0 was
shifted into the rightmost position. In the second case, the rightmost 1 was shifted out (perhaps
into the carry flag), and a new 0 was copied into the leftmost position, preserving the sign of the
number. Multiple shifts are sometimes shortened to a single shift by some number of digits. For
example:

00010111 LEFT-SHIFT-BY-TWO
= 01011100

A left arithmetic shift by n is equivalent to multiplying by 2n (provided the value does not
overflow), while a right arithmetic shift by n of a two's complement value is equivalent to
dividing by 2n and rounding toward negative infinity. If the binary number is treated as ones'
complement, then the same right-shift operation results in division by 2n and rounding toward
zero.

[edit] Logical shift

Main article: Logical shift

In a logical shift, the bits that are shifted out are

discarded, and zeros are shifted in (on either
end). Therefore, the logical and arithmetic left-
shifts are exactly the same operation. However,
the logical right-shift inserts bits with value 0
instead of copying in the sign bit. Hence the
logical shift is suitable for unsigned binary Logical shift right Logical shift left
numbers, while the arithmetic shift is suitable
for signed two's complement binary numbers.

[edit] Rotate no carry

Main article: Circular shift

Another form of shift is the circular shift or

bit rotation. In this operation, the bits are
"rotated" as if the left and right ends of the
register were joined. The value that is shifted
in on the right during a left-shift is whatever
value was shifted out on the left, and vice
versa. This operation is useful if it is
Right circular shift or rotateLeft circular shift or rotate
necessary to retain all the existing bits, and is
frequently used in digital cryptography.

[edit] Rotate through carry

Rotate through carry is similar to the rotate no
carry operation, but the two ends of the register
are considered to be separated by the carry flag.
The bit that is shifted in (on either end) is the
old value of the carry flag, and the bit that is
shifted out (on the other end) becomes the new Right rotate through carryLeft rotate through carry
value of the carry flag.

A single rotate through carry can simulate a logical or arithmetic shift of one position by setting
up the carry flag beforehand. For example, if the carry flag contains 0, then x RIGHT-ROTATE-
THROUGH-CARRY-BY-ONE is a logical right-shift, and if the carry flag contains a copy of the sign
bit, then x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE is an arithmetic right-shift. For this reason,
some microcontrollers such as PICs just have rotate and rotate through carry, and don't bother
with arithmetic or logical shift instructions.

Rotate through carry is especially useful when performing shifts on numbers larger than the
processor's native word size, because if a large number is stored in two registers, the bit that is
shifted off the end of the first register must come in at the other end of the second. With rotate-
through-carry, that bit is "saved" in the carry flag during the first shift, ready to shift in during
the second shift without any extra preparation.

[edit] Shifts in C, C++, C#

In C-inspired languages, the left and right shift operators are "<<" and ">>", respectively. The
number of places to shift is given as the second argument to the shift operators. For example,

x = y << 2;

assigns x the result of shifting y to the left by two bits.

In C and C++, computations with the left operand as an unsigned integer use logical shifts. In
C#, the right-shift is an arithmetic shift when the first operand is an int or long. If the first
operand is of type uint or ulong, the right-shift is a logical shift.[2] In C, the results with the left
operand as a signed integer are:[3] In general case:

x = a << b then x = a*2^b;

x = a >> b then x = a/2^b;

 for "<<": y×2right (undefined if an overflow occurs);

 for ">>": implementation-defined (most often the result of the arithmetic shift: y/2 right).

There are also compiler-specific intrinsics implementing circular shifts, like _rotl8, _rotl16,
_rotr8, _rotr16 in Microsoft Visual C++.

[edit] Shifts in Java

In Java, all integer types are signed, and the "<<" and ">>" operators perform arithmetic shifts.
Java adds the operator ">>>" to perform logical right shifts, but because the logical and
arithmetic left-shift operations are identical, there is no "<<<" operator in Java. These general
rules are affected in several ways by the default type promotions; for example, because the eight-
bit type byte is promoted to int in shift-expressions,[4] the expression "b >>> 2" effectively
performs an arithmetic shift of the byte value b instead of a logical shift. Such effects can be
mitigated by judicious use of casts or bitmasks; for example, "(b & 0xFF) >>> 2" effectively
results in a logical shift.

[edit] Shifts in Pascal

In Pascal, as well as in all its dialects, for example Object Pascal and Standard Pascal, the left
and right shift operators are "shl" and "shr", respectively. The number of places to shift is given
as the second argument to the shift operators. For example,

x := y shl 2;

assigns x the result of shifting y to the left by two bits.

[edit] Applications

Bitwise operations are necessary for much low-level programming, such as writing device
drivers, low-level graphics, communications protocol packet assembly, and decoding.

Although machines often have efficient built-in instructions for performing arithmetic and
logical operations, in fact, all these operations can be performed by combining the bitwise
operators and zero-testing in various ways.

For example, here is a pseudocode example showing how to multiply two arbitrary integers a
and b (a greater than b) using only bitshifts and addition:

c := 0
while b ≠ 0
if (b and 1) ≠ 0
c := c + a
shift a left by one
shift b right by one

return c

This implementation of ancient Egyptian multiplication, like most multiplication algorithms,

involves bitshifts. In turn, even addition can be written using just bitshifts and zero-testing:

c := b and a
while a ≠ 0
c := b and a
b := b xor a
shift c left by one
a := c
return b