[Tutorial] Bitwise Operators

[zylum]

Bitwise Operators Tutorial:

Beginner:

Prerequisite:

Before we start off, we need an understading of the binary representation of numbers.
We know numbers in their base 10 form. This means that there are 10 digits which we
can represent numbers in. Binary is a base 2 system, therefore all the numbers must be
represented using the digits 0 and 1. You can convert binary to decimal using a simple
fact about binary numbers. Each digit in a binary number is a power of two. If you sum
the value of each digit in a binary number, you will get the base 10 number as a
result. The least digit (the one furthest to the right) is the 0th digit, therefore
its base 10 value is 2^0 or 1. The next digit is the 1st digit and its value is 2^1 or
2. This applies to all following digits. Lets take a look at an example:

code:

convert 11001101 to base 10. = 2^7 + 2^6 + 0 + 0 + 2^3 + 2^2 + 0 + 2^0 = 128 +  64 + 0 + 0 +   8 +   4 + 0 +   1 = 205

Operators:

There are six different bitwise operators offered in turing. These include:

- & 'bitwise and'
- | 'bitwise or'
- ~ 'bitwise compliment / bitwise not'
- xor 'bitwise exclusive or'
- shl 'bitwise shift left'
- shr 'bitwise shift right'

When you apply these operations on any number, the individual bits of the number are
being manipulated. When you 'and' two numbers, you compare each bit in the numbers, if
they are both high (1) then the resulting bit will be high, otherwise the resulting
bit will be low (0). 'Or-ing', 'not-ing', or 'xor-ing' two numbers are similar
operations but have different outcomes depending on what the two bits are. Here is a
table that show the result of each comparision:

code:

X  Y  | X and Y   |  X or Y  | not X  |  not Y  |  X xor Y         |           |          |        |         |   1  1  |    1      |    1     |   0    |    0    |     0   1  0  |    0      |    1     |   0    |    1    |     1   0  1  |    0      |    1     |   1    |    0    |     1   0  0  |    0      |    0     |   1    |    1    |     0

Due to the interesting characteristics of the xor opperation, you can do some
interesting things. For example, if you have a very limited amount of memory to work
with and you need to swap two variables without using a third variable, you can use
the xor operator:

code:

var a : int := 392 var b : int := 9374 a := a xor b b := a xor b a := a xor b put a put b

Cool huh?



Bit shifting:

The shl and shr operators shift all the bits in your number by a specified number of
steps in a specified direction. If you shift all the bits of a number to the left by
one, you have just multiplied your number by two. If you shift them once right, then
you have divided by two. When you shift right, any bit going past the least bit will
be truncated, therefore you cannot get decimals from shifting right. This operation
is equivalent to dividing something by two using the div operator. That is to say the
decimals will be truncated. On the other hand if you are shifting left, you will be
introducing extra leading zeros where the least bit used to be. Lets take a look at
some examples:

code:

235 shl 1 = 11101011 shl 1 = 111010110 = 470 235 shr 1 = 11101011 shr 1 = 1110101 = 117

You can also shift bits by more than one step. Each step has a magnitude of 2^steps.
That is to say, if you perform a shifting operation, it will be equivalent to
multiplying or dividing by 2^steps, depending on which direction you are shifting.
So 1 shl 4 = 1 * 2^4 = 16.



Intermediate:

Isolating Bits:

So now you know how binary works. What if you want to look at a specific bit in a
number? You can use the 'and' operator and your knowledge of how it works to look
at any bit. Say you have a variable N and want to see if the 5th bit is high. You
would shift 1 to the left by 5 steps and and the resulting value with the variable N.
If the fifth bit in N is high, then the result of the and operation will be greater
than zero because both fifth bits were high those the result will have a high fifth
bit. To be more precise, the result will equal 2^(5-1) or 1 shl (5-1), but it will
suffice to check whether it is greater than zero rather than compute that value each
time. Example:

Find the value of the 6th bit in variable N:

code:

var N := 2#1110110   //86 put (N & (1 shl 5))  //results 32 N := 2#1010110 put (N & (1 shl 5))  //results 0

Practicle Example:

Although you have probably rarely to used these operators, they do come in handy.
For example, if you have multiple flag variables and you manipulate and compare them
frequently with each other, you can instead store them in a single variable.

A good example of where you may need lots of flags is in an RPG. You can have a single
variable that stores whether or not a character is wearing a type of equiptment, say
armour. What you can do is have a bunch of constants that represent each item:

code:

const weapon1 := 1 const weapon2 := 2 const boots := 4 const armour := 8 const helm := 16 const gloves := 32 const ring1 := 64 const ring2 := 128 const amulet := 256 var player : nat := 0 player := player | boots | helm | weapon1 | ring2

First thing to notice is that each equipment constant is a power of two. This is very
important because each bit in a number is a power of two. To put on a peice of
equipment, you simply need to "or" it on to your player. You can put on multiple
peices of equipment by "chaining" all the "ors" as above. So in the above example,
the player would be wearing boots, a helm, a weapon in slot one and a ring on finger
two.

You can effectively use bitwise operations to easily check certain aspects of your
player. For example, to check if your character is naked, you simply need to check if
your player variable is equal to zero. This would mean that none of the bits are high
and the resulting variable equals zero. You can check if the player is equiped with
a combination of items like so:

if (player & (armour | helm | gloves | boots)) = (armour | helm | gloves | boots) then

This chechks if player is wearing all of those items. If you want to check if he is
wearing at least one of a set of items (such as a peice of jewelery) then you would
do something like this:

if (player & (rign1 | ring2 | amulet)) > 0 then

This would check if the player is wearing a ring or an amulet. This is because if any
of the bits in player match with the active bits in any of the jewelery constants,
then then result will be greater than one.



Advanced:

An interesting property about binary is that if you count from zero to N, where N can
be represented as 2^m-1 where m is a positive integer, you will generate all posible
combinations of 0 and 1 of length m. This can be a useful property for some bruteforce
problems.

Bitmasking:

As discussed above, you can use binary in bruteforce problems when you need to
generate all combinations of a list. Lets look at an example problem:

You have an array of positive integers which represent the size of a file. You also
have an integer Size which represents the size of a CD that you have. You want to find
what is the most amount of data that you can put on the CD.

Solution: First thing to observe is that you want try every combination of files. A
combination consists of a series of files that you want to put on the disc. These
combinations can be represented as a binary number consisting of N bits where N is
the number of files you have. Each bit in the binary number will tell you whether or
not the file should be used in the current combination. So to generate all the
combinations, all you have to do is count from 0 - 2^N-1 and isolate each bit to see
if that file should be added to the current combination:

code:

var files : array 1 .. 10 of int := init (24, 235, 41, 21, 353, 61, 431, 927, 81, 46) var N : int := 700 var best : int := 0 for i : 0 .. 2 ** upper (files) - 1 %loop through every combination     var temp : int := 0  %stores the sum of the files in current combination     for j : 1 .. upper (files)  %loops through each bit         if (i & (1 shl (j - 1))) > 0 then  %checks the bit if it is high             temp += files (j)  %adds the file to the sum         end if     end for     if temp <= N and temp > best then  %checks whether the current combination is better then the current best         best := temp     end if end for put best

Expert:

Note: the following discussion will be dealing with 64 bit data types ie long long in
C++ etc. This data type is not available in turing but the same concepts apply to
smaller data types aswell. Furthermore, you can use two 32 bit 'nat' variables to
represent a long long.

Chess:

Many board games can be represented with a series of two dimensional boolean arrays
which keep track of where peices lie on the board. For example, in chess, you can
have two sets of boards which represent peice configurations for black and white. You
would also need an array to store the entire board. In each set of arrays, you can
have an array which keeps track of all the pawns, one to keep track of where the
enemies peices are attacking, etc.

Dealing with so many arrays can be a hasle, especially since you *really* need all of
these representations when making an AI for chess. Having all of this information
readily available can make your AI run much faster. But how can we improve upon this
concept?

Well, if we have a 64 bit data type like a long long, we can represent an 8x8 chess
board using each of its bits. The first problem that arises is how do we know which
bit corrisponds to each square on the chess board and vise versa? Well we can create
a simple function that assigns a unique value to each square on the board so that we
can 'or' them on to our variables. Remember, each bit is a power of two from 0 - 63
so therefore each square on the chess board must represent a number from 0 - 63:

code:

fcn chess2bit (row, col : int) : nat     result ((row - 1) * 8 + col - 1) end chess2bit proc bit2chess (bit : int, var row, col : int)     row := bit div 8 + 1     col := bit - (row - 1) * 8 + 1 end bit2chess var r, c : int put chess2bit (2, 6) bit2chess (13, r, c) put r, " ", c

So to add a peice to the square (2,3), you would 'or' the bit which represents that
square:

code:

var chessBoard : nat chessBoard := chessBoard | (1 shl chess2bit(2, 3))

To remove a peice, you 'and' the compliment of that bit:

code:

chessBoard := chessBoard & (~(1 shl chess2bit(2, 3)))

So what are the advantages of using bits to represent your various boards? For one
thing, bitwise operations are usually faster because they are done at a machine level
(this is not the case for turing). Furthermore, you can utilize the bitwise operations
to your advantage to manipulate each board in such a way you wouldnt be able to do
using arrays. For example, say you have two variables, one storing the positions of
the white peices and one for the black. If you 'or' these to values, you will get a
value representing the entire chess board. Another example: If you have a board
representing the places where a certain peice can move, and you have a board
representing where that peice cannot move (ie another peice in the way), you can 'xor'
these values and then then and the result with the peice's legal moves. The result
will be LEGAL moves for that peice. This comes in handy if you want to move your king
and you have a board representing where all the opponents peices can attack, you can
easily find the moves for the king where he wont be in check. Not only are these
operations more convenient, if you have a 64bit processor you get an even greater
speed boost.



Conclusion:

You probably have not encountered bitwise operations yet and they seem a bit abstract,
keep an open mind and use them whenever you can. They come with interesting and
useful attributes aswell as they can make your programs run faster. In some situations
you can greatly simplify your problem by using these operators.

I hope this tutorial has shed some light on these mysterious operators and hopefully
inspired you to use them. I know this tutorial covered each topic quite breifly so if
you have any questions shoot away!

[Mr. T]

Solid job.

[TokenHerbz]

Holly crap i dont get any of that...

One thing at a time here... im working on class's/2d array mapping, reading n writing files...

This has got to wait!!

But good job, looks awsome.

[ZeroPaladn]

I got everything up to the [i]shl[\i] part. Very well done, and very professional. I'd give ya bits, but, alas, i learned my lesson last time
you're a mod.

[beard0]

Excellent tutorial. I did some programming in assembly over the summer, and so am quite aware of bitwise operators, but had not thought of their useful application in higher level languages. You make some excellent points! I found my jaw dropping a little as I saw the completely logical way of easily manipulating the data (if you'll excuse the pun).

[zylum]

glad you enjoyed it

[A.J]

once again, amazing job zylum!
could you post a follow up with some more of the uses of these operators (or just tell me some practice problems involving bitmasking for practice, other than tetris )

[zylum]

The most common use is for the subset problem which is described in the tutorial. Bitwise operators are also useful for adhock problems like the tetris problem. For practice here's a problem off the top of my head:

You are given two ribbons. One long ribbon contains black and white stripes where as the second shorter ribbon contains opaque and transparent stripes. The first ribbon will be described by a length and then a set of intervals describing the locations of the black stripes. The second ribbon will be described the same way but the intervals will describe where the opaque stripes are located. Your job is to determine how many ways you can place the smaller ribbon on the longer ribbon such that none of the black stripes are blocked by the opaque stripes of the shorter ribbon. The shorter ribbon must be completely on the longer ribbon.

[A.J]

could u give me an example please?
(P.S: This is my 100th post )

[zylum]

Ribbon 1:
Length = 10
Stripe Locations = { (2, 3), (5, 7), (8,9) }

Ribbon 2:
Length = 3
Opaque Locations = { (2, 3) }

so Ribbon 1 looks like this:

code:

-#--##-#--

Ribbon 2 looks like this:

code:

-#-

Your solution should return 4.

code:

-#- -#--##-#--   -#- -#--##-#--      -#- -#--##-#--        -#- -#--##-#--

[A.J]

Nice!
I'll work on it and send you the solution (if u don't mind ) when I am done!
thnx once again!

[jacksmith]

A bitwise runs on one or more bit patterns or binary numerals their individual bits. It is a quick and primitive action supported directly by the processor and is used to manipulate values ​​for comparisons and calculations. Simple and inexpensive, are binary operations usually processors faster than division, is many times faster than multiplication and sometimes much faster than addition.

[nullptr]

Here's something interesting: x & -x will give you the lowest-value bit of x. For example, 48 & -48 gives 16, since 48 can be written as 110000, and so the lowest-value bit is 10000, which equals 16. Not sure if that explanation made sense, but I thought it was pretty cool.