RNA On Binary! Bitwise Operations included(!,&,|,^,<&

RNA · Post by **RNA** » 04 Jul 2007, 04:24

Binary, and Bitwise Operations

WARNING: Expect some odd english choices, it's 4:15AM give me a break! There may be some Errors too

For those who dont know binary, here we go!

a bit is either 1 or 0. On or Off, etc.
Binary is base two
I will use comparisons of base10 which is what we all learned.
now, base 10 works in that, every 10 the next didgit goes up one.
for example:
..7...8..9..10
that digit is set to 0 and the next didgit.
in base 2, it goes like this
0..1...10...11...100... so on.(0->1->2->3->4)

Now, Binary is in the powers of two(beacuse each one has TWO options! tricky!)
now, knowing our powers of two we can see this:
working from right to left(the lowest is always on the right in numbers, as you notice)
we have 2**0(** is power, from here on out) for our first bit, which is 1.
our second bit is 2**1, or 2
the third would be 2**2 or 4
so on and so forth.

so lets look at say, 10:
1010

Code: Select all

1  0  1  0 :Binary
8  4  2  1 :Base10(for each bit)
3  2  1  0 :Powers of 2!(for each bit)

using the powers system, it is easy to convert to binary, or from binary. To convert from binary is simple addition.
To convert to binary, is somewhat harder.
First, find the highest power of 2 that goes into the number, lets say our test number is 36.
the highest power that goes into 36 of 2 is 32.
so we take 32 from our 36 and we have 4 left
so our first bit is 1
next power down, 16. 4-16 is negative, so that bit is 0
next power down, 8, 4-8 is negative, so that bit is 0
next power down, 4, 4-4 is 0, so that bit is 1
next power down is 2, 0-2 is negative, so that bit is 0
next power down is 1, 0-1 is negative, so that bit is 0

and we have: 100100

now a BYTE is 8 bits(bits and bytes!)
which means the highest a BYTE can store is 255(1+2+4+8+16+32+64+128)or, one less than the next power of two(256)

So now you might understand binary somewhat, hopefully you can practice and convert most numbers in your head.

So, some of us know binary, but how about operations?

Lets move on to our bitwise operations,
these operations are done on two series of bits.

Our first operations: NOT ,AND, OR and XOR (Common Programming language abriviations are !,&,|,and ^ respectivly(not to be confused with logical AND and logical OR (&&,||))

NOT:
NOT makes each bit its oposite, simple enough.

Code: Select all

! 1010
  0101

AND:
AND takes two and where both inputs have a 1, the result is a 1
Example:

Code: Select all

1011 & 0111

1011  (11)
0111  (7)
____
0011  (3)

OR:
OR takes two and where either inputs have a 1, the result is a 1
Example:

Code: Select all

1011 & 0111

1011 (11)
0111 (7)
____
1111 (15)

XOR:
XOR is like or, except that it is exclusive. One, the other, but NOT both.

Code: Select all

1011 ^ 0111

1011 (11)
0111 (7)
____
1100 (12)

XOR is great, infact, here is a way to swap variables without using a temp variable using XOR, if you can explain it to me, you get a cookie

Code: Select all

//C++ code

void swap(int &x, int &y)
{
	if(x != y)
	{
		x ^=y;
		y ^=x;
		x ^=y;
	}
}

Great, So now you've seen the operations! Note how I did the one over the other? the Drop down method makes doing these calculations VERY easy! Its like Binary Tetris

So, now we have Shifts!

A shift is simple, we take a byte, and we shift it, either left or right!

in C++ / Java the syntax is << or >> depending on the direct( left or right respectivly)
Note, in C++/Java they use Logic Shifts, bits that 'slide off' are not placed on the other end.

Examples!
the syntax is as followed
var << ammount;

Code: Select all

//x = 10001011
x=x << 1;
//x = 00000110
//remeber that bits that shift off the byte are gone. gone gone away :(

//y = 11111111
y = y >> 2;
//y = 00111111

shifts are useful, use could use them to say, store 2 4bit items in one byte. simply add the first 4bit item, shift left 4, then add the next 4.
You can also store an entire RGBA(Red Green Blue Alpha) sequence in a 32bit integer!
Here is a small little comparison chart for binary to base10/base16(aka hex)
binary is base2, if you didn't gather

Code: Select all

BASE10 -> BASE2
1  :00000001	
2  :00000010
4  :00000100 
8  :00001000
16 :00010000	
32 :00100000
64 :01000000 
128:10000000
255:11111111

Hex -*gt; Binary:

Code: Select all

Remeber, most system's ints are 32bits long, the largest I did in this was one byte(8bits)

I leave you with this great piece of knowledge.

256 is the same as 2 to the 8th
which is the same as 2 to the(2 to the 3rd)
which is the same as 2 to the (2 to the [(2 to the 1)+1])
which is the same as 2 to the (2 to the [(2 to the 2[2 to the 0]) + 2 to the 0])
2**[2**(2**2**0 + 2**0)]

or a more simple
16 is the same at 2**4
2**4 == 2**(2**2)
Everything is dripping with 2s. Everthing.
Binary is everywhere you look, EVERYWHERE!

~RNA

Post by **ayu** » 04 Jul 2007, 05:04

Nicely done =)

I asume you are bored at this hour? ^^

RNA · Post by **RNA** » 04 Jul 2007, 06:29

When one cant sleep due to an obsession with 2s, one writes about binary.

Atleast I do things

Post by **bad_brain** » 04 Jul 2007, 08:41

well done!

Post by **Gogeta70** » 05 Jul 2007, 00:30

Very informative and well written. Great job!