World of Bits and Bytes

| Comments

Recently, I have realized that no matter how much C, C++ or other high level languages you know it all comes down to bit and bytes view of program.
I started realizing that after all it’s not that easy to actually think and write in bit/byte manipulation. This is my attempt to learn and be more comfortable about thinking in bit/bytes.

Basics

Introduction here



Bit & Byte 
 1
 2 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0
 3||              |               |               |              ||
 4|+- bit 31      |               |               |       bit 0 -+|
 5|               |               |               |               |
 6+-- BYTE 3 -----+--- BYTE 2 ----+--- BYTE 1 ----+-- BYTE 0 -----+
 7|                               |                               |
 8+----------- WORD 1 ------------+----------- WORD 0 ------------+
 9|                                                               |
10+--------------------------- DWORD -----------------------------+
11
12Hexadecimal Numbers
130 1 2 3 4 5 6 7 8 9 A B C D E F


Bitwise Operators

Operators Bitwise Operations 
 1
 2The & operator (AND)
 31   &   1   ==   1
 41   &   0   ==   0
 50   &   1   ==   0
 60   &   0   ==   0
 7
 8The | operator (OR)
 91   |   1   ==   1
101   |   0   ==   1
110   |   1   ==   1
120   |   0   ==   0
13
14The ^ operator (XOR)
151   ^   1   ==   0
161   ^   0   ==   1
170   ^   1   ==   1
180   ^   0   ==   0
19
20The ~ operator
21The ~ (Ones Complement or inversion) operator acts only on one value
22and it inverts it.
23
24The << (Left Shift)
2500001100  - b 
2600110000  - b << 2
27
28The >> (Right Shift)
2900001100  - b
3000000011  - b >> 2
31
32Another example is
331<<4; 0001 0000


Bit Fields

 1struct date-struct {
 2BYTE day   : 5,   // 1 to 31
 3     month : 4,   // 1 to 12
 4     year  : 14;  // 0 to 9999
 5} date
 6
 7|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 |
 8  |                           |       |         |
 9  +------ year ---------------+ month +-- day --+
10
11date.day = 12;
12dateptr = &date;
13dateptr->year = 1852;

Basics of Binary Arithmetic


Problems

How set a single bit in a byte?

For e.g In byte 0000 1000 set bit no 6 will produce 0100 1000
(Remember bit number starts with 0-7)

Set Bit 
 1
 2//For problems where certain bit values needs to be changed, first we
 3//need to create a bit mask.
 4//Bit mask is a temporary variable with some value. Using this value
 5//we will access and change specific bits in a byte of data.
 6
 7//For e.g.
 8//To set 6th bit in a byte 0000 1000
 9//We have             MASK 0100 0000  (OR)
10//                    ——————————————
11//                         0100 1000
12
13//To turn on certain bit in a byte (OR) is used.
14
15int set-bit(int val, int num, bool bitval)
16{
17    return (val | (bitval << num));
18}
19//Here, val    = 0000 1000 = 8
20//      num    = 6 (set 6th bit)
21//      bitval = 1 (set to 1)
22
23//      0000 1000
24//(OR)  0100 0000  (1 << 6)
25//      ————————-
26//      0100 0000


How to unset single bit in a byte?

For e.g In byte 0100 1000 unset bit no 6 will produce 0000 1000
(Remember bit number starts with 0-7)

Unset Bit 
 1
 2//To unset specific bit we will use (AND) operation.
 3//Mask value need to be ‘0’ for the bit to unset but rest of the bits
 4//need to ‘1’. The reason for rest of the bits to set as ‘1’ is as
 5//we are doing (AND), we don’t want to unset other bits which are
 6//already set.
 7//
 8//For e.g.
 9//To unset 6th bit 0100 1000
10//            MASK 1011 1111 (AND)
11//                ——————————-
12//                 0000 1000   (Result)
13int unset-bit(int val, int num, bool bitval)
14{
15    return (val & ~(bitval << num));
16}
17
18//Here, val    = 0100 1000
19//      num    = 6
20//      bitval = 0
21//      (bitval << num) = 0100 0000
22//     ~(bitval << num) = 1011 1111
23//
24//      0100 1000
25//      1011 1111 (AND)
26//      —————————-
27//      0000 1000    (Result)


One function to set and unset

Set & Unset Bit 
1
2int change-bit(int val, int num, bool bitval)
3{
4    return (((val & ~(bitval << num)) | (bitval << num));
5}


Unset range of bits

Unset range of bits Bitwise Operations 
Unset range of bits
For e.g. 1001 1001
Unset bits from 2 to 5 i.e. 1 0 0 1 1 0 0 1 => 10 0000 01
                               |- - - -| 
                      Bits  7 6 5 4 3 2 1 0          

Step1
------
To unset range of bits we need to create MASK
 val  = 1001 1001
 Mask = 1100 0011 (AND)
      _____________
        1000 0001

Step 2
-------
We need to construct MASK
In MASK, bits in range are 0 i.e. bits from 2-5 is 0 and
rest of the bits are 1
 MASK 1 1 0 0 0 0 1 1
         |- - - -|
 Bits 7 6 5 4 3 2 1 0

Step 3
-------
 0 0 0 1  1 1 1 1  ((1 << 5) - 1) i.e. (1 << j) - 1

MAX  1 1 1 1  1 1 1 1
     0 0 1 1  1 1 1 1  (-)
    ------------------
     1 1 0 0  0 0 0 0         =====> (1)

 (1 << 2) - 1 i.e. (1 << i) - 1
 0 0 0 0 0 1 0 0
 0 0 0 0 0 0 0 1 (-)
------------------
 0 0 0 0 0 0 1 1                   =======> (2)

 (1) OR (2)
 1 1 0 0 0 0 0 0
 0 0 0 0 0 0 1 1   (OR)
-------------------
 1 1 0 0 0 0 1 1 

Final Step
 val  = 1001 1001
 Mask = 1100 0011 (AND)
      _____________
        1000 0001
unsetBitsInRange Bitwise Operations 
 1
 2// i is start of range
 3// j is end of range
 4int unsetBitsInRange(int val, int i, int j) {
 5    int max = ~0;
 6
 7    int left = max - ((1 << j) - 1);
 8
 9    int right = (1 << i) - 1;
10
11    int mask = left | right;
12
13    return (val & mask);
14}


Set range of bits

Set range Range Unset Mask 
This mask is similar to Range Unset Mask created earlier with an 'exception'
in last

/***********************************************************
//In "Range UNset Mask" we created following
//For e.g. 1001 1001
//Unset bits from 2 to 5 i.e. 1 0 0 1 1 0 0 1 => 10 0000 01
//                               |- - - -| 
//                      Bits  7 6 5 4 3 2 1 0    
//Step1
//------
//To unset range of bits we need to create MASK
// val  = 1001 1001
// Mask = 1100 0011 (AND)
//      _____________
//        1000 0001
***********************************************************/
 
We will be creating the same mask in addition we will 
TOGGLE the bits of "unset mask"

 Unset MASK = 1100 0011
 TOGGLE     = 0011 1100    ~(Unset Mask)

 Now perform OR will val
 val  = 1001 1001
 Mask = 0011 1100 (OR)
      _____________
        1011 1101
setBitsInRange 
 1
 2// i is start of the range
 3// j is end of the range
 4int setBitsInRange(int val, int i, int j) {
 5    int max = ~0;
 6
 7    int left = max - ((1 << j) - 1);
 8    int right = (1 << i) - 1;
 9
10    int mask = left | right;
11
12    return (val | ~mask);  
13}


Recomended readings

Posted by Vaibhav Gautam binary numbers

« Binary number operations sorting »

Comments