-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0|368|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Article Home -> Advanced Techniques


 
Phoenix
Created : 15 August 2007
Edited : 07 October 2007

Binary numbers

Ever wondered what those 1's and 0's meant?

Introduction
This tutorial will cover binary numbers, bitwise operations and their practical uses. There are many programmers who overlook the usefulness of binary numbers, but the truth is that sometimes they can be really handy.

What are binary numbers?
If you already know what binary numbers are and how they relate to our regular number system, you can skip this section.

The binary number system is also known as the base 2 numbers system, because it only has 2 different digits to create numbers with, our system being base 10 since it has 10 digits we can combine. Normally, we use the decimal (base 10) system, which counts from 0 to 9. After nine, we start adding the numbers together, but since binary numbers only count from 0 to 1, it never gets to 9. Instead, we add the numbers when it reaches two. So:

Binary Decimal
0 0
11
10 2
113
100 4
1015


There is no digit for ten in the decimal number system, since it only counts to nine, so what do we do? We add another column of numbers, and when we reach 99 we need to add yet another column. That's the principle we use when counting in binary numbers too. Number two doesn't exist as a binary number, therefore we add another column of numbers after 1, and then a new one after 3 etc.

Bitwise operations
Bitwise operations work like the basic arithmetics; addition, subtraction etc. Except that the bitwise operations work with binary numbers. All the operations work on one bit at a time (a bit is a binary digit, 1 or 0).

And
This is the first one we're going to look at. Let's say we have the binary number 1101. If we and it, with 1011, we'd get 1001. Why, you probably ask. And checks one bit at a time from both of the binary numbers, and compares them. If both of them equals 1, then the result will have 1 at the same position as the compared values. Confusing? Maybe this will explain better:



If you take a look at the first column, you see that both of the numbers are 1, which makes the first number in the result one as well. But in the next column, Value1 shows 1 while Value2 shows 0. They don't match, so the next number in the result will be zero. The same thing happens in the next column, except that the numbers are reversed this time. Hopefully you can figure out why the last column becomes one

Or
Or works a bit like and, but it is less picky; while and requires both bits to be 1, or only wants at least one bit to equal 1. To illustrate:



Not
This has to be the simplest of them all, it simply inverts the binary number. One becomes zero and vice versa. What makes not different from the other operations is that it only needs one value, it doesn't compare anything.



Xor
Xor means exclusive or. Unlike the not operation, xor uses two values to calculate it's result. It compares the two bits, and if they are different, it gives us a 1. If they are the same, it gives a zero.



Practical usages of the operators
Now here comes the interesting part - why do I need to know all this stuff? My first example is bit flags. I have coded a small example in Blitz, which should be easy to convert to any language.



Since bits are either 1 or 0, they can be seen as boolean values (true or false). And by having a binary number, you can combine many boolean values into just one variable, by making each bit represent either true or false. These binary numbers are called bit flags.

You might see that at the top of the program, I have defined a lot of constants, with a lot of names for colors. The idea is that we should be able to combine color values into one variable, and then see if a color is stored in it. Maybe you're wondering why the constants have the values they have? Why assign them 1, 2, 4, 8, 16 and 32 instead of just writing 1, 2, 3, 4, 5, 6? Pick up the windows calculator, and enable scientific mode at the view menu if it isn't already turned on. Then type in 1, and click the radio button saying "Bin". It still says one, because 1 in decimal converted to binary becomes 1. Fairly straight forward, but go back to the decimal system and type in two. Now it says 10; just an extra zero. If you repeat the process with the remaining numbers (4, 8, 16 and 32), you see that every time you convert to binary, it adds another zero. So:



That's why we're using those numbers; because that way every flag gets it's own column. For example, if the flags with the values 4 and 32 are activated, we get 100100. The first 1 indicating that the flag with value 32 is activated, the two zeros following showing that flags 16 and 8 are deactivated etc.

Great, so how do we retrieve the values? Surprisingly easy, actually. To see if a bit is activated in a bit pattern, we simply use and on the binary number with the flag(s) we want to check.



The result is 100, since the flag was activated. We can also combine many values using or and test them against the full pattern. Take a look at my example to see it all in action.

I have another example that works a bit like the bit flags, which demonstrates not.



The blocks represent the bits in the bit pattern, try pressing space to see them inverted by not. The actual drawing code isn't very important, but I think the example illustrates quite well how binary numbers are represented.

Bit shifting
Bit shifting is a very simple concept, it works a bit like multiplication/division. By performing a left shift on a binary value, move all the bits one step to the left. For example:



All the bits were moved one step to the left once, multiplying the number by two. Guess what happens if you perform a left shift twice. That's right - you move the bits two steps to the left. Which in the previous example would make the result 100101100 (an extra zero at the end). The right shift does the opposite, moving all the bits to the right, dividing the number.



Bitwise operators in different languages
Blitz 2D/3DBlitz MaxPure BasicVB.NETC/C++/C#/Java/PHP/RubyDelphi
AndAndAnd&And&and
OrOrOr|Or|or
Not~~~Not~not
XorXor~!Xor^xor
Left shiftShlShl<<<<<<shl
Right shiftShrShr>>>>>>shr


Note: In BlitzMax, xor is used this way: a~b. Not is used without any value preceding the ~ sign, e.g. ~a.

Useful tips
  • 000100 is the same as 100! Sounds like a silly thing to point out but I always messed up when I first learned about binary numbers.
  • Performing a left/right shift is slightly faster than multiplying/dividing, so if you're speed hungry you should try to use bit shifting.
  • With some clever thinking, you can compress a lot of data using bit flags. Check out Agent Smith's code in comment section of this code snippet: socoder.co.nr/&snippet=4071.
  • In Blitz, you can use binary numbers by prefixing them with a %, for example %1001110.

Exercises
Here are some exercises for you, to see if you understood the article. Please solve them without cheating; no calculator or googling!

Exercise 1: Try to figure out what the binary number 1010 means in the decimal system.

Exercise 2: What is the result of 11011 and 10101?

Conclusion
I hope you learned something from this article, it became a little longer than I thought. But read it all, it's definitely useful to know about this stuff. I'll add more tips/exercises if I can think of any.

 

Comments


Wednesday, 15 August 2007, 18:44
mike_g
Heres a nice line of code I found the other day:

It halves a colour value and 'ands' out the high R, G, and B bit. Allowing pixel shading, whilst avoiding RGB colour conversions.
Wednesday, 03 October 2007, 07:47
lyons
what a nice little artical, it took like a week for a collage lecturer to explain dat last year
---
oops forgot to vote
Wednesday, 03 October 2007, 09:04
JL235
Thank you!!! I didn't know about the ~, and so this solves one of my all time hates about Blitz's incorrect boolean precedence. Thanks again!
Wednesday, 03 October 2007, 10:53
mike_g
In C/C++ the bitwise not/inverter is actually ~ as well. ! is the logical not operator.
Wednesday, 03 October 2007, 11:28
Phoenix
Ah, thanks mike_g. I stand corrected

|edit| I wonder though, what's happened with the last code box? It shows something completely different to what I've written. I suspect there's something fishy going on in the code... |edit|

|edit| I just removed the code box, that seems like a nice solution for now.|edit|
Wednesday, 03 October 2007, 17:00
Agent
Here's a little binary-to-ASCII conversion function I wrote in C (hope you don't mind me posting it here Phoenix).


Thursday, 04 October 2007, 12:04
Phoenix
Quite the opposite; it's great that you're posting it That's a clever way to do it, I wouldn't have thought of that.
Saturday, 06 October 2007, 14:51
Phoenix
I extended the bitwise operator list and added some more languages. However, most languages tend to stick to the &, |, ~, ^, <<, >> operators.
Saturday, 06 October 2007, 18:16
Agent
In BlitzMax, the bitwise ~ operator is both (unary) Not and (binary) Xor. There's also Sar (shift arithmetic right), which is similar to Shr but extends the sign bit.

PureBasic uses ! for bitwise Xor.
Sunday, 07 October 2007, 04:46
mike_g
Sar also features in Blitz Basic. Its what was used in that colour blending function I posted to avoid losing data when shifting the sign bit.