Solid job.
Computer Science Canada [Tutorial] Bitwise Operators |
| Author: | zylum [ Mon Oct 10, 2005 3:40 pm ] | ||||||||||||||||||||
| Post subject: | [Tutorial] Bitwise Operators | ||||||||||||||||||||
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:
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:
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:
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:
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:
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:
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:
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:
So to add a peice to the square (2,3), you would 'or' the bit which represents that square:
To remove a peice, you 'and' the compliment of that bit:
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! |
|||||||||||||||||||||
| Author: | Mr. T [ Mon Oct 10, 2005 5:34 pm ] |
| Post subject: | Alex's Opinion |
Solid job. |
|
| Author: | TokenHerbz [ Mon Oct 10, 2005 11:14 pm ] |
| Post subject: | |
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. |
|
| Author: | ZeroPaladn [ Tue Oct 11, 2005 9:21 am ] |
| Post subject: | |
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. |
|
| Author: | beard0 [ Tue Oct 11, 2005 11:10 am ] |
| Post subject: | |
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). |
|
| Author: | zylum [ Tue Oct 11, 2005 4:20 pm ] |
| Post subject: | |
glad you enjoyed it |
|
| Author: | A.J [ Tue Mar 11, 2008 9:59 pm ] |
| Post subject: | Re: [Tutorial] Bitwise Operators |
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  ) |
|
| Author: | zylum [ Tue Mar 11, 2008 11:57 pm ] |
| Post subject: | RE:[Tutorial] Bitwise Operators |
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. |
|
| Author: | A.J [ Tue Mar 11, 2008 11:59 pm ] |
| Post subject: | Re: [Tutorial] Bitwise Operators |
could u give me an example please? (P.S: This is my 100th post ) |
|
| Author: | zylum [ Wed Mar 12, 2008 12:11 am ] | ||||||
| Post subject: | RE:[Tutorial] Bitwise Operators | ||||||
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:
Ribbon 2 looks like this:
Your solution should return 4.
|
|||||||
| Author: | A.J [ Wed Mar 12, 2008 12:15 am ] |
| Post subject: | Re: [Tutorial] Bitwise Operators |
Nice! I'll work on it and send you the solution (if u don't mind ) when I am done!
thnx once again! |
|
| Author: | jacksmith [ Tue Jul 23, 2013 5:11 am ] |
| Post subject: | Re: [Tutorial] Bitwise Operators |
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. |
|
| Author: | nullptr [ Tue Jul 23, 2013 12:50 pm ] |
| Post subject: | Re: [Tutorial] Bitwise Operators |
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. |
|