The magic of bits "Bitwise"

Introduction to bitwise - date: 24/11/2011

Art by Kev Walker

The story tale

Before the long tale to the course of magic bits, let's go for a little walk in the world of C language. In C, the bitwise operators allow you to manipulate individual bits in a value. This can be useful for certain low-level operations, such as setting or checking the value of a specific bit in a flag. For example, you could use a bitwise operator to set the fourth bit in a value to 1 without affecting the other bits. This can be useful for optimization and make your code more efficient by allowing you to perform certain operations using bit manipulation instead of more complex methods. Additionally, the use of bitwise operators can make your code more compact and easier to read because you can perform multiple operations using a single operator instead of using multiple lines of code. Variable of type int has 4 bytes, so 32bits.

If we do it:

"int var = 3;"

We can see this schema:

4bytes = 32bits

Looking at this context, each octet is a byte. Half an octet can be called a nibble.

“…00000000 00000000 00000011”

Each place of a binary number counts as one bit. The bit is nothing but a mnemonic for “Binary digiT”. So to know the number of bytes, we use the “sizeof(var)” operator, which returns the value in bytes of the variable. If we want to know the binary value of a number, we divide by 2, and as long as the remainder of the division is different from “1”, we divide the end. We take the leftovers in reverse to be the final result, for example, number 12:

12 | 2
12 +------                   1100 --> reverse result
 0  6    | 2              -------------
         +-----
    0      3  | 2
              +-----
          1     1
 

Going on, there's another better way to do it, but no it's time to address this now.

#include <stdio.h>
 
 
int main()
{
 int bin[8],num=0,counter=0;
 
 puts("Dec2Bin\n digite um numero");
 scanf("%d",&num);
 
 while(num!=1)
 {

  bin[counter]=(num%2)?1:0;

  num/=2;
  counter++;
 }
 bin[counter]=num;
 
 printf("\nResultado: ");
 while(counter!=-1)
 {
  printf("%d",bin[counter]);
  counter--;
 }
 printf("\n");
 
 return 0;
}
 

Introduction to "Bitwise" When we say bitwise, it is a mere reference to work to manipulate bits to get specific results. Staff who work with microcontrollers, AVR and PIC often have to do such manipulation. When we want bitwise performance, we can also help, although the compiler already optimizes many tasks. Another use is in image processing and manipulation. OpenCV even forces you to use it whenever there is no ready-made solution.

So looking at C language, the left shift operator "<<" shifts the bits of a value to the left by a specified number of positions. This has the effect of multiplying the value by a power of 2. For example, if you shift the value 4 left by 1 position, the result would be 8 because 4 * 2 = 8.

Looking to another hand, the right shift operator ">>" does the opposite, shifting the bits of a value to the right by a specified number of positions. This has the effect of dividing the value by a power of 2. For example, if you shift the value 8 right by 1 position, the result would be 4 because 8 / 2 = 4.

One motivation for using the left shift and right shift operators is to perform multiplication and division by powers of 2 quickly and efficiently. This can be useful for optimization, especially in time-critical operations where every clock cycle counts. Another motivation is to use these operators to manipulate individual bits in a value, which can be helpful for various purposes, such as setting or checking the value of specific bits in a flag.

Shifting is nothing more than changing the bit from its original position. To get a specific result, we call this technique bit shift a mnemonic of the assembly “shl”(shifting left) and shr(shifting right). Let's look at an example of shifting to the left:

int var = 3;
var <<= 1;
So the 3
 0011
recv left shift
 0110

The result is “6”, which can give an illusion of product arithmetic or addition by itself, but it was the result of displacement, formed correctly according to the K&R math textbook to explain our expression. An example would be “2*3¹”.

Now look that following a shift to the right:

int var = 100;

So you can see 1100100

var >>= 2;
remove last two digits
 11001

The result gives us “25” the mathematical form for this is the following “(100/2)²”.

You tell me 25 thousand. Where are the zeros? As I said, remove the last two digits.

Bit mask

OR

Let's go to the “|” operator with the “OR” mnemonic in assembly. Let's go to understand its impact.

x=26|19;
  11010
| 10011
---------
  11011   ==  27

AND

Now the “&” mnemonic with “AND” in assembly.

x=26&19;
  11010
& 10011
---------
  10010 == 18

The "~" is mnemonic with "NOT"; that is, it is a negation, making an inverse effect of its loaded value, where one is, it becomes zero and vice versa. So the result would be -27, Like, but why not 5? Remember that I said an "int" is 4 bytes equals 32bits, so look at the following:

0000 0000 0001 1010

1111 1111 1110 0101

I did it in a nibble, so I don't have to write too much.

XOR

The “^” is a mnemonic for XOR.

x=26^19;
  11010
^ 10011
---------
  01001  == 9

So look at that table in the following:

,---,---,--------,
| a | b |  a ^ b |  in this point you can make SWAP  
|---|---|--------|  example:
| 0 | 0 |   0    |
| 0 | 1 |   1    |  int A=4,B=7;
| 1 | 0 |   1    |  A^=B; B^=A; A^=B;
| 1 | 1 |   0    | 
'---'---'-------cc

The magic of the bits

Let's use bitwise to get "performance" let's go to get

some bitwise code snips.

// one line to check if a value is even or odd
main(int argc,char *argv[]){printf("%s\x0a",(!((atoi(argv[1]))&1))?"odd":"even");}
// This "x&1" same effect like "x%2"
 
// num is multiple
resto = num & (divisor - 1);
x = 122 % 6;
// maybe faster
x = 122 & (6 - 1);
 
/*
casting float to Int
"x = int(3.142)" try to "x=3.142>>0;" can be improve the performance
*/
// ternary operation
i = x < 0 ? -x : x;
// try
i = (x ^ (x >> 31)) - (x >> 31);
 
// compare ints
x = a * b > 0;
// or try
x = a ^ b >= 0;
 
//Compare two vars
gamma = y ^ ((x ^ y) & -(x < y)); // equivalent to gamma=menor(x, y)
gamma = x ^ ((x ^ y) & -(x < y)); // equivalent to  gamma=maior(x, y)
 
//check 2 potence
x = v && !(v & (v - 1));

//average number to integer
int a=6,b=8; printf("%d\n",((a&b)+(a^b)>>1));
 
// check if exist position "n" in bit "1"
if( n & 1 << i ) 

So remember our simple code to convert decimal to binary? Let's make one using bitwise 🙂

// https://github.com/CoolerVoid/C/
char * dec2bin(int n, char * string)
{
 int i;
 static int size = 8 * sizeof(int);
 
  for(i = size - 1; i >= 0; i--, n >>= 1)
   string[i] = (01 & n) + '0';
 
 string[size] = '\0';
 return string;
}

The square root calc, following bitwise path:

// header beer.h https://github.com/CoolerVoid/C/edit/master/beer.h
int bit_sqrt(int num)
{
//so 32 is sizeof(int)<<3 -1="" bit_sqrt="" error="" if="" int="" num0="num,result=0,tbit=1<<((sizeof(int)<<3)-2);" num="" printf="" return="" tbit="" while="">num0)
  tbit>>=2;
 while(tbit^0)
 {
  if(num0>=result+tbit)
  {
   num0-=result+tbit;
   result=(result>>1)+tbit;
  }else
   result>>=1;
  tbit>>=2;
 }
 return result;
}

This function cannot be compared to APIs such as GMP and OpenSSL even because it is a simple function, much less “math.h” it was more to illustrate.

Can I use bitwise on strings?

If it is a pointer, why not?

// return reverse string
char *strrev(char *str)
{
 char *p1, *p2;
 
 if(! str || ! *str)
  return str;
 for(p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
 {
  *p1 ^= *p2;
  *p2 ^= *p1;
  *p1 ^= *p2;
 }
 return str;
}

So this second example is a simple benchmark following CPU cycles to compare arithmetic division using bitwise and common resources.

/*
Author: Cooler_
Contact: coolerlair[at]gmail[dot]com

Compares arithmetic division with bitwise and without
test CPU cycles and soon

$ gcc -o code code.c; ./code 
*/
#include <stdio.h>
#include <stdlib.h>
#include <x86intrin.h>
#include <cpuid.h>
#include <inttypes.h>
 
#define LAST "\033[0m"
#define RED "\033[22;31m"
 
void mul()
{
 int x=50,y=0;
 while(x)
 {
  y=x*2;
  x--;
 }
}
 
 
void leftshift()
{
 register int x=50,y=0;
 while(x)
 {
  y=x<<1 bit_div7="" div7="" n="" num="" register="" return="" unsigned="" x--="" x="(num" y="">>1)+(num>>4);
 x+=x>>6;
 x+=(x>>12)+(x>>24);
 x>>=2;
 y=num-((x<<3 return="" x="" y="">>3);
}  
 
 
unsigned div3(unsigned n)
{
 return n/3;
}
 
// 
unsigned bit_div3(unsigned num)
{
 register unsigned x,y;
  
 x=(num>>2)+(num>>4);
 x+=x>>4;
 x+=x>>8;
 x+=x>>16;
 y=num-((x<<2 ficou="" return="" ruim="" x="" y="">>5);
// ruim  return x+( (y+5+(y<<2>>4);
 return x+( (((y+1)<<2 y="">>4);
 
}
 
 
 
int main(void)
{
  int x=0;
  uint32_t a=0, b=0, c=0, d=0;
  register uint64_t y=0;
 
  x = 0;
  do {
    __cpuid(0, a, b, c, d);
    y = _rdtsc();
    leftshift();
    y = _rdtsc() - y;
  } while (++x < 2);
 
  printf("::: left shift: %s  %lld %s cicles\n",RED, y,LAST);
 
 
  x = 0;
  do {
    __cpuid(0, a, b, c, d);
    y = _rdtsc();
    mul();
    y = _rdtsc() - y;
  } while (++x < 2);
 
  printf("::: mul: %s %lld %s cicles\n", RED,y,LAST);
 
 
  unsigned int z=0;
 
  x = 0;
  do {
    __cpuid(0, a, b, c, d);
    y = _rdtsc();
    z=div7(560000*x);
    printf("result: %d\n",z);
    y = _rdtsc() - y;
  } while (++x < 2);
 
  printf("::: div7: %s %lld %s cicles\n", RED,y,LAST);
 
  z=0;
  x = 0;
 
  do {
    __cpuid(0, a, b, c, d);
    y = _rdtsc();
    z=bit_div7(560000*x);
    printf("result: %d\n",z);
    y = _rdtsc() - y;
  } while (++x < 2);
 
  printf("::: bit_div7:  %s %lld %s cicles\n",RED, y,LAST);
 
 
  x = 0;
  do {
    __cpuid(0, a, b, c, d);
    y = _rdtsc();
    z=div3(560000*x);
    printf("result: %d\n",z);
    y = _rdtsc() - y;
  } while (++x < 2);
 
  printf("::: div3:  %s %lld %s cicles\n",RED, y,LAST);
 
  z=0;
  x = 0;
 
  do {
    __cpuid(0, a, b, c, d);
    y = _rdtsc();
    z=bit_div3(560000*x);
    printf("result: %d\n",z);
    y = _rdtsc() - y;
  } while (++x < 2);
 
  printf("::: bit_div3:  %s %lld %s cicles\n", RED,y,LAST);
 
 
 
  exit(0);
}

This subject is huge. I'll stop here for the end. I suggest you read it to delve deeper into the subject by bitwise, the following book “hacker’s delight".

References

Hacker's DelightAmazon.com

The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision DiagramsAmazon.com

Thank you for reading, cheers!