Binary numbers

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0|514|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-

SoCoder -> Article Home -> Advanced Techniques

Phoenix

Created : 15 August 2007
Edited : 07 October 2007

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
1	1
10	2
11	3
100	4
101	5

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:

Using and on the following values:
Value1: 1101
Value2: 1011
------------
Result: 1001

--v

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:

Using or on the following values:
Value1: 1001
Value2: 1100
------------
Result: 1101

--v

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.

Using not on the following value:
Value:  1001
------------
Result: 0110

--v

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.

Using xor on the following values:
Value1: 1001
Value2: 0011
------------
Result: 1010

--v

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.

; Flags
Const BITFLAG_RED    = 1
Const BITFLAG_GREEN  = 2
Const BITFLAG_BLUE   = 4
Const BITFLAG_YELLOW = 8
Const BITFLAG_PURPLE = 16
Const BITFLAG_BLACK  = 32

; Combine the any flags
BitFlags = BITFLAG_BLACK Or BITFLAG_BLUE

; Show test results
Print "Bitflags are red and blue: " + BitflagHasColors( BitFlags, BITFLAG_RED Or BITFLAG_BLUE  )
Print "Bitflags are blue: " + BitflagHasColors( BitFlags, BITFLAG_BLUE )
Print "Bitflags are green and black: " + BitflagHasColors( BitFlags, BITFLAG_GREEN Or BITFLAG_BLACK  )
Print "Bitflags are black and blue: " + BitflagHasColors( BitFlags, BITFLAG_BLACK Or BITFLAG_BLUE )
Print "Bitflags are black, blue and red : " + BitflagHasColors( BitFlags, BITFLAG_BLACK Or BITFLAG_BLUE Or BITFLAG_RED )

WaitKey()
End

; Returns true if the bitflag(s) passed contains the requested color(s)
Function BitflagHasColors( flags, col )
	; Simply by using And on flags and col we see if the result equals the color(s) we wanted
	If( (flags And col) = col ) Then Return True
	
	Return False
End Function

--v

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:

Using or:
   100 (4)
  1000 (8)
 10000 (16)
100000 (32)
-----------
111100

--v

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.

And the following
100100 (all the bit flags combined)
000100 (see if flag 4 is activated, which is blue in my code)
------
000100

--v

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.

; Bin is used to prevent Blitz from converting %1011010111 to 727 (it's decimal equivalent)


; Try changing this value and see the result
tileRow = %1011010111

; Not really necessary to understand
; Just calculates the amount of bits in the bit pattern
rowLength = Len( Mid( Bin( tileRow ), Instr( Bin( tileRow ), "1" ) ) )

While( Not KeyHit( 1 ) )
	; Outline the row
	Rect( 32, 0, rowLength * 32, 32, 0 )
	
	; Loop through every bit in the row, one bit at a time
	For i = 1 To rowLength
		; If the bit is turned on (1) then draw a rectangle
		If( Mid( Right( Bin( tileRow ), rowLength ), i, 1 ) = "1" )
			Rect( i * 32, 0, 32, 32 )
		EndIf
	Next
	
	; If space is pressed we invert the bit pattern using not (~)
	If( KeyHit( 57 ) ) Then tileRow = ~tileRow
	
	; Show the pattern using text
	Text( 32, 34, Right( Bin( tileRow ), rowLength ) )
	
	Flip()
	Cls()
Wend
End()

--v

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:

Left shift once:
Value:  01001011
Result: 10010110

--v

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.

Right shift once:
Value:  1001011
Result: 0100101

Right shift twice:
Value:  1001011
Result: 0010010

--v

Bitwise operators in different languages

	Blitz 2D/3D	Blitz Max	Pure Basic	VB.NET	C/C++/C#/Java/PHP/Ruby	Delphi
And	And	And	&	And	&	and
Or	Or	Or	\|	Or	\|	or
Not	~	~	~	Not	~	not
Xor	Xor	~	!	Xor	^	xor
Left shift	Shl	Shl	<<	<<	<<	shl
Right shift	Shr	Shr	>>	>>	>>	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:

 col = (col Shr 1) And 8355711

--v

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).

/* btoa: convert integer to ASCII string as binary number */
void btoa(const int b, char *a)
{
  register unsigned long mask = 1, binary = b;
  while (binary >>= 1)
    mask <<= 1;
  while (mask) {
    *a++ = b & mask ? '1' : '0';
    mask >>= 1;
  }
  *a = '\0';
}

--v

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.