CHAPTER 6 - Bit arithmetics


This is what most tutorials usually start with. After reading this you will be confused, it is normal, you will get this by usage. Return to this chapter whenever needed. So let's go.

6.1. Encoding number in bits
You know computer uses "bits", which are variables that can contain one of two possible values, 0 or 1. When value of bit is 0, we say it is "clear", when it is 1, we say it is "set"

terms:
bit - variable containing 0 or 1
clear bit - bit containing 0
set bit - bit containing 1
Now how can we store number in such bits. It is similar to storing word in two bytes (chapter 4.2, reread it). One bit contains value 0 or 1, so number that consists from only one bit can contain only values 0 and 1. When we add another bit, we can still store 0 and 1 in first bit, but we have another bit which now can hold 2*(0 or 1). Then another bit holds 4*(0 or 1), then 8*(0 or 1) etc.

Like i said before, byte consists of 8 bits. So it can hold value
1*(0 or 1)+2*(0 or 1)+4*(0 or 1)+8*(0 or 1)+16*(0 or 1)+32*(0 or 1)+64*(0 or 1)+128*(0 or 1) which is value from 0 (when all bits are 0) to 1+2+4+8+16+32+64+128 = 255 (when all bits are 1). See it?

It is similar for word, just with 16 bits instead of 8, check it yourself if you wish.

Now some terms: bit which holds 1*(0 or 1) is bit 0, next, which holds 2*(0 or 1) is bit 1, and so until bit 7 which holds 128*(0 or 1). So bits are enumerated from 0, not from 1 as you would maybe await. bit 0 is called "low order bit", highest bit (which holds greatest value) is "high order bit". For example high order bit of some byte value is bit 7, and high order bit of word value is bit 15.
terms: low-order bit, high-order bit
important: bits are enumerated from 0, not from 1, so first bit is bit#0

Number encoded this way (in bits) is called "binary number".


6.2. Binary constants
You was using numeric constants before probably without deeper realizing you are using them. Numeric constants were just numbers you wrote in source file which were assembled into binary file. Numeric constants are for example "0", "50", "-100", "123456".

You used them here: 
db 5
mov al,20
cmp ax,5
db 'Some string',0
org 256
These numbers were decimal: ones which are used by (?) normal people. Assembler then translated them to binary form. But sometimes you want to specify directly binary numbers. Of course you dont have to hand-translate to decimal, you can specify them directly binary. Here are some examples of binary numbers: 0, 101011, 1101011, 11111, etc. To differ them from decimal numbers, every binary number must end with "b" character, so "0b", "101011b", "1101011b", "11111b" etc. Here first binary digit (first bit, first 0 or 1) is high-order bit, last one is low-order bit. So if you write "1101", then bit 0 = 1, bit 1 = 0, bit 2 =1, bit 3 = 1.

Example table:
decimalbinary
0 0b
1 1b
2 10b
3 11b
4 100b
5 101b
6 110b
7 111b
10 1010b
15 1111b
1610000b

I could learn you way how to translate number between decimal and binary forms, but you wont need it now anyway, and all other tutorials are full of such informations.

Binary numeric constants are just another way to express some number. Writing "5" is same as writing "101b". For example this will work too: 
org 100000000b
mov ah,1001b
mov dx,string
int 21h
int 20h
string db 'Hello world writen using binary constants',0
org 100000000b is same as org 256, and mov ah,1001b is same as mov ah,9


6.3. Bit operations
Now let's think about what we can do with bit (which can hold value 0 or 1).

First, we can "set" it (set it's value to 1) or "clear" it (set it's value to 0). Then we can "flip" it's value (from 0 to 1, from 1 to 0). And that is probably all. This operation is called "bit complement" too (0 is complement of 1, 1 is complement of 0)

(lack of english math terms here, somebody could help me)

Now what we can do with 2 bits? If you think of bits as about boolean values, which can be either true (1) or false (0). Now what operations can we make with boolean values? If you programmed before you probably know this.

First is and (like "a and b" where "a" and "b" are boolean values :). When we have two boolean values, result of anding them is true only when they are both true, otherwise result if false. (Table will be below)

Then comes or. You know, result of oring two values is true, when at least one of them is true. And last, least known, is xor, which means "exclusive or" (the previous one was "inclusive or", but everyone calls it just "or"). Result of xoring is 1 when one operand is 1 and other is 0.

Here is the table:
ABA and BA or BA xor B
00 0 0 0
01 0 1 1
10 0 1 1
11 1 1 0

NOTE: There are 16 possible operations on two bits but we wont talk about them all.

Now interesting (?) part: In late times, processors designers didnt like having lot of instructions on their processors. But as you see, we defined 3 operations for single bit and 3 for two bits. So they found (obvious) way to achieve operations on single bit by using operations on two bits. To remind: operations on single bit were setting it to 0, setting it to 1 and flipping it's value (0->1, 1->0). How?

First let's talk about clearing bit (setting it's value to 0). Note that result of and is 0 whenever at least one of operands is 0. So if we and any bit (0 or 1) with 0 we always get 0, when we and with 1 bit will reamin unchanged. And this is what we wanted. It is similar with setting bit (to 1). Result of oring is 1 when at least one of operands is 1. So oring any bit with 1 will always produce 1, oring with 0 will leave bit unchanged.

How to flip bit? Result of xoring is 1 when one of operands is 1, other 0. So xoring any value with 1 will always produce value's complement, xoring with 0 will leave bit unchanged. This one is not so obvious, so better look at it in table.


6.4. Binary operation instructions
First of all. You know smallest register we have are 8 bit (byte) registers. Also smallest part of memory we can access is byte (8 bits). For this reason binary operation instruction we will use will operate on two 8 bit numbers instead on two bits. What will be result? Bit 0 of result will be result of operation between bit 0 of first argument and bit 0 of second argument. Bit 1 of result will be result of operation on bits 1 of argument etc. You 'll see it.

First operation will be "and". Example: 
mov al,00010001b
mov bl,00000001b
and al,bl
first we load al with 00010001b, so it's bits 0 and 4 contain 1, other bits contain 0. Then we load bl with 00000001b so it's bit 0 contains 1, other contain 0. Now when we and al with bl (this is how asm coder usually tells it), it works like some al = al and bl would eg. result of anding al with bl is stored in al.

So what is the result (in al)? Bit 0 of al contained 1 and was anded with 1. "1 and 1" is 1, so bit 0 of al will be 1. Bits 1 to 2 and 5 to 7 would be "0 and 0" which is 0. Bit 3 would contain "0 and 1" which is 0 too. Bit 4 will contain "1 and 0" which is 0 again. So result would be 00000001b. Better way to write previus code would be 
mov al,00010001b
and al,00001001b
(i used bl in previous example only to reference second number easier in text).

Now oring: 
mov al,00010001b
or  al,00001001b
result will be 00011001b, due to or description (one subchapter upwards).

And xoring: 
mov al,00010001b
xor al,00001001b
result will be 00011000b. Bits xored with 0 will remain, bits xored will 1 will be flipped (to their complement).
instructions: and, or, xor
These instructions take same arguments as mov eg. first argument can be memory variable or register, second can be memory variable, register or constant. Both arguments must be of same size, only one of arguments can be memory variable.

6.5. Testing bits.
If you was programming before, you probably already know about boolean variables (rarely called logical). They can hold two values, TRUE or FALSE. You see that they can be finely stored in bit, 1 for TRUE, 0 for FALSE.
term: boolean variable
Problem here is, that smallest data directly accessible is byte (8 bits). You know, you can access byte register or byte memory variable, not bit. This is really so, there are no instruction which just access one bit. (Of course there are, you just don't need to know about them now :).
But when you work with boolean variable you want to access only one bit, not all 8 bits or more. There are some tricks to do this:

Use only one bit of whole byte and leave other bits cleared. Thus if you want to see if bit is 0, you just check if whole byte is equal to 0. If it is not, then our bit is 1. Example: 
cmp [byte_boolean_varaible],0
je byte_boolean_variable_is_false
jnz byte_boolean_varaible_is_true
where byte_boolean_variable is byte varaible with only one bit used. If such variable is 0 then value is FALSE, otherwise value is TRUE.
byte_boolean_variable_is_*** are labels used for branching as shown in previous chapter. By the way better "more assembly" way to do same as previous is: 
  cmp [byte_boolean_varaible],0
  je byte_boolean_variable_is_false
byte_boolean_varaible_is_true:
  <here value is TRUE>
byte_boolean_varaible_is_false:
  <here value is FALSE>
beacause in first version jnz conditonal jump would be always taken, because instruction is executed only when je wasn't taken. If you dont understand read previous chapter.

But using this way there are 7 unused bits, and that is waste of space. (Not for single variable, but surely for array of such variables). It is clear we can "pack" 8 boolean varaibles into single byte (8 bits). Problem is only setting and reading it.

First, we'll set all 8 bits (boolean variables) using mov instruction. 
mov [eight_booleans],00000000b
this would set all variables to zero (clear them). If we want set some of them to one, we just set bits in which they are stored. 
mov [eight_booleans],00010100b
this will set variables in bits 2 and 4, and leave all ather clear.

First, how to clear one bit and leave all other unmodified? We solved this before, we can do this with "and"ing: 
and [eight_booleans],11110111b
This will clear bit 3 (anded with 0 so result will be 0), and leave all other bits unchanged (anded with 1 so will stay unchanged). This will clear bits 3 and 5: 
and [eight_booleans],11010111b
it should be clear if you comprehended chapter 6.4.

Now how to set one of variables: 
or [eight_booleans],00001000b
This sets bit 3 to 1 (oring with 1 always gives 1) and leave other unchanged (oring with 0 leaves unchanged).

And, of course, using xor we can flip bit(s): 
xor [eight_booleans],00001000b
will flip bit 3 and leave others.

This was just to remind you, now let's go to checking value of bit. Checking value of bit is called "testing bit".
term: testing bit
You often need to test value of some boolean variable and do something (jump somewhere) if it is (or isn't) TRUE. We did this with byte-sized boolean variable using cmp instruction, but it is impossible to use cmp for testing only one bit of byte. For this reason, there is test instruction. It takes same arguments like mov, xor, and, cmp etc. It ands it's operands and if result of anding is 0 then it sets flags so that if result is zero then je will be taken, if result isn't zero je won't be taken (and jnz would). 
test arg1,arg2
acts a little like 
and arg1,arg2
cmp arg1,0
but it doesn't modify arg1 and you use jz (jump if zero) and jnz (jump if not zero) conditional jumps. jz jumps if result of virtual anding (testing) is zero. Similary, jnz jumps, if result is not zero (eg. at least one tested bit is non-zero) NOTE: In fact, jz is same instruction as je and jnz is same as jne, so using jz is same as using je would be in and/cmp example
instruction: test
Some example of using test 
test [eight_booleans],00001000b
jz bit_3_is_clear
bit_3_is_set:
<...>
bit_3_is_clear:
<...>
all bits but third of eight_booleans are anded with 0 (but eight_booleans stays unmodified), which means they are cleared, only value of third will remain. Then result of operation will be zero (and je will taken) only if third bit is 0. If it is 1, result of operation will be 00001000b, not 0 so je won't be taken.

Now some little more dificult example: 
test [eight_booleans],00101000b
je bits_3_and_5_clear
bits_3_and_5_not_both_clear:
<...>
bits_3_and_5_clear:
<...>
bits 3 and 5 of eight_booleans will remain, so result of operation will be 0 (and je will be taken) only when both these bits are 0. If at least one of these bits is 1 result won't be 0 (it can be 00001000b or 00100000b or 00101000b) and jz won't be taken. But testing two bits at one time usually isn't used, at least not by beginners, i gave this example just for better picture how test works.