View source

'''Bitwise operations'''

There are certain operations that you can use on individual bits or groups of bits. These operations are called '''bitwise operations''' and the operators we use to perform them are called '''bitwise operators'''.

There is a clear distinction between bitwise operators and bitwise instructions. Bitwise ''operators'' are symbolic operators that we shall use for clarifying operational concepts. Bitwise ''instructions'' are the equivalent machine instructions provided by the microprocessor to simulate these operators.

The ''logical bitwise instructions'' for 80386 and higher microprocessors are NOT, AND, OR, XOR, TEST, BSF, BSR, BT, BTC, BTS, BTR, and SETcc. These aid in manipulating bit values. Additional instructions, called the ''bit manipulation instructions'', that aid in moving bits include SHL, SAL, SHR, SAR, SHLD, SHRD, ROL, ROR, RCL, and RCR. Since their uses are important to every programmer, a good grasp of the bitwise operations, operators, and their machine-equivalent instructions is essential to learning ASM.


'''WHY USE BITWISE OPERATORS'''

There are several reasons why we need to or should use bitwise operators. One of the most popular ones is: most programmers prefer using the individual bits of a variable as boolean options for their code rather than using separate boolean variables as shown in an example (not asm code) below. This saves memory space and speeds up the application program.

; Instead of using separate variables like this :
<pre>
bShowAmbientLight = TRUE
bNoSound = FALSE
bNoVideo = TRUE
bNoSeek = TRUE
.
.
.
</pre>

We could create a variable
   dwCodeOptions

; and assign options to its bits like this :
<pre>
bit 0 to bShowAmbientLight
bit 1 to bNoSound
bit 2 to bNoVideo
bit 3 to bNoSeek
and so on...
</pre>

So, whenever bit 2 in dwCodeOptions is ''set'' to 1, the video preview will not be shown. If it were ''cleared'' to 0, then videos will be enabled. The same applies for the other options.

'''Setting, clearing, and toggling bits'''
''Setting'' a bit means changing its value to 1, while ''clearing'' a bit means changing its value to 0. By ''toggling'' a bit, we mean changing its current boolean value to the other boolean value. If it is currently 1, then toggling it will change it to 0. Knowing these terms is quite essential for understanding how to apply the operators discussed below.

'''Number of Options'''
The number of bits you can use as boolean options in your code is limited by the size of the variable you use for storing them. If you create a 32-bit (DWORD-sized) variable, then 32 bits are available for use as boolean options. Creating a 16-bit (WORD-sized) variable will only allow for 16 bits to be used. Similarly, 8-bit (BYTE-sized) variables will restrict your options to 8 bits.

'''Bit Masks'''
A bit mask is a temporary value that we use while setting, clearing, and toggling bits. As an example, see the one discussed under the AND Operator heading.


'''THE LOGICAL OPERATORS'''

'''NOT bitwise operator'''

NOT is probably the easiest bitwise operator to understand. The NOT operator is an unary operator, meaning that it takes only one operand. NOTing a value results in changing it to its opposite--NOT toggles values. If you NOT 1, you get 0. If you NOT 0, you get 1.

<pre>
NOT(0) = 1    ; NOT changes "I am not going" to "I am going"
NOT(1) = 0    ; NOT changes "I am going" to "I am not going"

; The parentheses only suggest that NOT is unary.
</pre>

It should be noted, however, that NOT toggles the values of all the bits its operand contains. If you want to toggle the values of specific bits in an operand directly, you can use the XOR operator instead as discussed a little later.

''Example'':
<pre>
  NOT 1100 1011b
  -------------
  =   0011 0100b

  NOT 0101 0111b
  ------------
  =   1010 1000b
</pre>


'''''Assembly Syntax'''''
<source lang="asm">
MASM:
NOT reg/mem

HLA:
NOT( reg/mem );
</source>


'''''Use the NOT instruction to:'''''
* Toggle all the bits in a value to get its 1's complement. To get the 2's complement use the NEG instruction or add 1 to the 1's complement.

'''''Don't do this:'''''
* ''NOT is not equal to NEG.'' NOT a = NEG a - 1 or NEG a = NOT a + 1. Never confuse the NOT instruction with the NEG instruction in assembly language.  NOTing a value doesn't negate it but gives us the 1's complement (all bits flipped). The 2's complement notation is used to represent negative numbers by x86-based systems. The relationship between the two operations can be shown as below:

<pre>
; => 2's complement = 1's complement + 1
NEG(0101 1100b) = NOT(0101 1100b) + 1
</pre>

'''AND BITWISE OPERATOR'''

AND is quite simple to understand, in that when you AND a bit (one of two states) with another, if one of the bits is 0, the result would be zero. However if both bits are 1, the result would be 1.

''"To result in TRUE, AND requires that '''BOTH''' of its operands be TRUE."''


<pre>
0 AND 0 = 0     ; If both Mary AND Julia are not going to the party, then I am not going too.
0 AND 1 = 0     ; If Mary is not ready to go AND Julia is, then I am not going.
1 AND 0 = 0     ; If Mary is ready to go AND Julia is not, then I am not going.
1 AND 1 = 1     ; If both Mary AND Julia are going, then I am also going.
</pre>


''Example:''

<pre>
        0101 1110b
    AND 1010 1010b
    -------------
    =   0000 1010b

        1011 1110b
    AND 0001 0101b
    -------------
    =   0001 0100b
</pre>


'''''Assembly Syntax'''''
<source lang="asm">
MASM:
AND dest, src
AND reg/mem, reg
AND reg, reg/mem
AND reg/mem, const

HLA:
AND( src, dest );
AND( reg, reg/mem );
AND( reg/mem, reg );
AND( const, reg/mem);
</source>


'''''Use the AND operator to:'''''
* ''Clear bits. ANDing a bit with 0, clears it.'' We use a temporary value called a ''bit mask'' for this purpose. Consider the conversion of lowercase letters to uppercase. The lowercase letters have binary representations wherein the 5th bit of any value is a 1. Each uppercase letter value has a 0 as its 5th bit. To convert 'a' (0110 0001b, 61h) to 'A' (0100 0001b, 41h), we use a bit mask with bit 5 as a 0 and the rest as 1s, so that it ANDs with the bit 5 (0) in 'a' to result in 'A'.

<pre>
        0110 0001b        ; 'a'
    AND 1101 1111b        ; bit mask with bit 5 = 0
    --------------
    =   0100 0001         ; which is 'A'
</pre>


'''OR bitwise operator'''

OR is somewhat the opposite of AND. When you OR a bit with another, if one of the bits is 1, the result will be 1. However if both are 0, the result would be 0.

''"To result in TRUE, OR requires that '''ONE OR BOTH''' of its operands be TRUE."''

<pre>
0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1
</pre>

''Example'':
<pre>
11100101b
01010111b OR
------------
11110111b

00000100b
10101010b OR
------------
10101110b
</pre>


'''''Assembly Syntax'''''
<source lang="asm">
MASM:
OR dest, src
OR reg/mem, reg
OR reg, reg/mem
OR reg/mem, const

HLA:
OR( src, dest );
OR( reg, reg/mem );
OR( reg/mem, reg );
OR( const, reg/mem );
</source>


'''''Use the OR instruction/operator to:'''''
* ''Set a bit. ORing a bit with 1 will set it.'' You'll use this operator very much when programming Windows. For example, when setting options for Window styles you use the OR operator. For more information, see the Windows ASM volume.

; * ''Compare the value in a register to 0''. Although, this is another little trick, it may prove useful and you may also see it used sometimes. It works because of the way the OR instruction affects the bits in the flags register. For example:

<source lang="asm">
; MASM
    OR eax, eax              ; equivalent to cmp eax, 0

; HLA
    OR( eax, eax );
</source>

is equivalent to eax comparing with 0 and sets the value of the Zero Flag bit in the flags register. You can then use a ZF-testing conditional jump (JNZ, JZ) to proceed with control flow. This instruction is equivalent to "cmp eax, 0", but since it produces shorter code, it is preferable to use it.

<source lang="asm">
cmp eax, 0                  ; compiles into 4 bytes - 66 83 F8 00
or eax, eax                 ; compiles into 3 bytes - 66 0B C0
</source>


'''XOR bitwise operator'''

XOR, or exclusive OR, is a binary operator like OR but with a slight difference. Frame what is said below, hang it on your favorite wall, and don't ever ask again.

''"To result in TRUE, XOR requires that '''ONLY ONE''' of its two operands to be TRUE."''

So, when you XOR two bits when both are valued 1, the result will ALWAYS be 0. XOR is used in some encryption technology such as XOR encryption (XOR encrpytion is weak) and for XOR swap. XOR allows you to swap the contents of two variables without using a third variable--only how we can do that is shown in actual code a little later.

<pre>
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
</pre>

; Example :
<pre>
       0011 1000b
   XOR 0011 1000b
   -------------
   =   0000 0000b


       0101 0101b
   XOR 1111 1000b
   -------------
   =   1010 1101b
</verbatim>


'''''Assembly Syntax'''''
<source lang="asm">
MASM:
XOR dest, src
XOR reg/mem, reg
XOR reg, reg/mem
XOR reg/mem, const

HLA:
XOR( src, dest );
XOR( reg, reg/mem );
XOR( reg/mem, reg );
XOR( const, reg/mem);
</source>


'''''Use the XOR instruction to:'''''
* ''Swap values.'' The x86 assembly XOR instruction allows us to swap two values without using a third placeholder. For example, to swap the values of the microprocessor registers eax and edx, you use the following XOR instructions.

<pre>
XOR  eax, edx
XOR  edx, eax
XOR  eax, edx
</pre>

Although this is a neat trick, the x86 already provides an XCHG instruction for swapping registers. This instruction is covered in the [[Data Transfer Instructions]] chapter.

Note also that the XOR instruction affects the x86 flags, whereas the XCHG instruction does not.
The XCHG instruction, when you supply a memory operand, has an implicit LOCK associated with it, which slows the execution of the instruction by a tremendous amount. Using XOR is a possibility when you don't want a bus lock associated with the XCHG operation.


* ''Toggle bits in a value.'' To toggle ''all'' the bits in 1000 1011b (to 0111 0100b) you can use NOT or you can XOR the value with -1 (1111 1111b). XORing the operand with -1 does exactly what NOTing it does. To toggle specific bits, you use a bit mask wherein the toggling bits should be valued 1, while the others should be 0. For example, to toggle bit 5 and bit 3 in 1011 0101b, we use 0010 1000b as the bit mask.

<pre>
; not code, only operator

       1011 0101b
  XOR  0010 1000b
  ---------------
  =    1001 1101b

; code it like this

XOR 10110101b, 00101000b
</pre>

; * ''Clear a register to 0.'' As interesting as it is, you can use the XOR operator to perform a very subtle operation that may not be very self-evident at first but is truly another marvel. XORing a register with itself will clear it to 0. Here's an example :
<source lang="asm">
   XOR eax, eax      ; same as "MOV eax, 0"
</source>

This instruction has the same effect as assigning 0 to the register. The above instruction has "MOV eax, 0" as its equivalent. However, "XOR eax, eax" is generally used (mostly to return 0 in conjunction with a RET directive). The reason it is used is that reg32 instructions are a little faster and much smaller.

; For example, "xor eax,eax" compiles as:
   66 33 C0

; while "mov eax,0" compiles as:
   66 B8 00 00 00 00

It occupies only 3 bytes as opposed to the 6 of the MOV version. The advantage to smaller instructions is that you can hold more in the instruction cache, speeding up program execution. Also, they require fewer memory fetches, which slow down programs as well.


* ''Detect errors and compute parity.'' ''Tricky XOR can "undo" itself.'' Exactly how it is done is explained a litte later, but first, let's answer: "What is parity?"

; ''Parity'' is " the state of being odd or even used as the basis of a method of detecting errors in binary-coded data " according to the Merriam-Webster Dictionary. Parity information is simply redundant information that is calculated from an actual set of values. Simply stated : ''If you have N values stored, you use these values to calculate an extra value (parity information) so that the number of values stored now becomes N + 1. If you happen to lose '''ANY ONE''' of the N + 1 values, you can recalculate it using the remaining N.''

''Parity can be odd or even.'' Parity is calculated by first counting the number of 1s in a unit of binary data, and then adding a 0 or a 1 (parity value) to make the count odd or even. In ''even parity'' the total number of 1s (including the parity value) should be even. In odd parity, the total number of 1s (including the parity value) should be odd.

''Example:''

<pre>
Consider the bits in 1001b:

   1. 1001 has 2 1-bits.

   2. We now add a parity bit to 1001.
        a. If we want even parity, number of 1s (incl. parity bit) should be even.
           So, the parity bit for 1001 in this case is 0, resulting in:

              1001 0       ;--- parity bit = 0

        b. If we want odd parity, number of 1s (incl. parity bit) should be odd.
           So, the parity bit for 1001 in this case is 1, resulting in:

              1001 1       ;--- parity bit = 1

Take another example, 1101b:

   1. 1101 has 3 1-bits.
   2. Add a parity bit:
      a. For even parity,

            1101 1      ;--- parity bit = 1

      b. For odd parity,

            1101 0      ;--- parity bit = 0
</pre>


'''SHR bitwise operator'''

SHR means shift right. Taking a number as a binary, and when SHR n is performed on it, all the bits would move right by n times. The uses for shift right are that when you shift right a number by n, it is like dividing the number by 2^n. Dividing on a computer is much slower than using shifts. Thus, it is better to replace divides with shift rights.

Example:
<pre>
01011010b SHR 3 = 00001011b
90 SHR 3 = 11

10101110b SHR 2 = 00101011b
174 SHR 2 = 43
</pre>


'''''Assembly Syntax'''''
<source lang="asm">
MASM:
SHR dest, cnt
SHR reg/mem, const
SHR reg/mem, CL

HLA:
SHR( cnt, dest );
SHR( const, reg/mem );
SHR( CL, reg/mem );
</source>


'''SHL bitwise operator'''

SHL means shift left. Taking a number as a binary, and when SHL n is performed on it, all the bits in the number would move left by n times. The uses for shift left are that when you shift left a number by n, it is like multiplying the number by 2^n. Multiplication on a computer is much slower than using shifts. Thus, it is better to replace multiplication with shift lefts.

Example:
<pre>
10010101b SHL 2 = 1001010100b
149 SHL 2 = 596

00011110b SHL 3 = 11110000b
30 SHL 3 = 240
</pre>


'''''Assembly Syntax'''''
<source lang="asm">
MASM:
SHL dest, cnt
SHL reg/mem, const
SHL reg/mem, CL

HLA:
SHL( cnt, dest );
SHL( const, reg/mem );
SHL( CL, reg/mem );
</source>