Binary Vectors

As a part of my master’s degree case study, I had given few questions in modulo arithmetic to implement as a pre-requisite for implementing a research paper. A few concepts in the document contains Binary vectors, Boolean functions, Walsh transform, Fast Walsh Transform and ANF and I thought I should blog about the same.

u >> i = (ui, ui+1 , . . . , um−1, 0, . . . )
u&v = (u0 ∗ v0 , . . . , um−1 ∗ vm−1)

For example, to get the first bit (u0 ) of an integer u, we can write u&1. Similarly, (u >> i)&1 gives the i-th bit (ui) of u

Question1:

Write a function taking as inputs an integer u (viewed as a binary vector) and an integer i, which returns the i-th bit of u?

Solution:
This is how an unisigned integer is represented in a 32 bit machine’s memory:

Value of first bit:

%%%%%%%%%% %%%%%%%%%%
0000000000000000 0000000000001010
%%%%%%%%%% %%%%%%%%%%

Unsigned int 10 is represented like ^^ in binary in a 32 bit machine/compiler. We are going to just do a logical and with ‘1’
%%%%%%%%%% %%%%%%%%%%
0000000000000000 0000000000001010 &
0000000000000000 0000000000000001
——————————————————
0000000000000000 0000000000000000

Value of ith bit:

Lets take 10, and this is how it is represented in binary

%%%%%%%%%% %%%%%%%%%%
0000000000000000 0000000000001010
%%%%%%%%%% %%%%%%%%%%

And lets say i is 2. After the first right shift
%%%%%%%%%% %%%%%%%%%%
0000000000000000 0000000000000101
%%%%%%%%%% %%%%%%%%%%

After the second right shift
%%%%%%%%%% %%%%%%%%%%
0000000000000000 0000000000000010
%%%%%%%%%% %%%%%%%%%%

In-order to find the value of ith bit, a logical AND operation is done to the last binary.
0000000000000000 0000000000000010 &
0000000000000000 0000000000000001
——————————————————
0000000000000000 0000000000000000

Source Code:

/* Written by Giri
   A function taking as inputs an integer u (viewed as a binary vector)
   and an integer i, which returns the i-th bit of u */

#include "header.h"
/* Functions are defined in util.c */

int main () {
	ulong u, i, choice;
	do {
		printf ("1. Check first bit\n");
		printf ("2. Check a random bit\n");
		printf ("3. Exit\n");

		printf ("Enter your choice: ");
		scanf  ("%lu", &choice);

		switch ( choice ) {
			case 1: printf ("Enter the integer: ");
					scanf ("%lu", &u);
					printf ("The first bit is %d\n", check_first_bit (u));
			break;

			case 2: printf ("Enter the integer: ");
					scanf ("%lu", &u);
					printf ("Enter the value of ith bit which you want to extract from the integer: ");
					scanf ("%lu", &i);
					printf ("The requested bit is : %d\n" , check_random_bit(u, i));
			break;

			case 3: 
					exit (0);
			break;

			default: printf ("00ps! Wrong choice!!\n");
			break;
		}
	} while ( ! ( choice  3 ) );
	return 0;
}

Question 2

Write a function returning the indice of the first non-zero bit of a binary vector.

Solution: We shift the binary vector until we get a 1 at the first bit of the same.

Source code:

/* Written by Giri
   A function returning the indice of the first non-zero 
   bit of a binary vector */

#include "header.h"
/* Status: Complete */
/* Function returns the indice of the first non-zero value
   in the given unsigned integer						*/
ulong find_indice ( ulong u) {
	if (u == 0UL)
		return ULONG_MAX;
	ulong indice = 0;
	while (!(u & 1UL)) {
		indice = indice + 1;
		u = u >> 1;
	}
	return indice;
}

int main () {
	ulong u;
	ulong choice;
	do {
		printf ("1. Check the position of first non-zero bit\n");
		printf ("2. Exit\n");

		printf ("Enter your choice: ");
		scanf  ("%lu", &choice);

		switch ( choice ) {
			case 1: printf ("Enter the integer: ");
					scanf ("%lu", &u);
					printf ("The indice of the first non-zero number is %lu \n", find_indice (u));
			break;

			case 2: 
					exit (0);
			break;

			default: printf ("00ps! Wrong choice!\n");
			break;
		}
	} while ( ! ( choice  2 ) );
	return 0;
}

Question3

A function that implements the Hamming weight of a binary vector

Solution:
Say the input is 1023:
%%%%%%%%%% %%%%%%%%%%
0000000000000000 0000011111111111
%%%%%%%%%% %%%%%%%%%%

1023 & ( 1023 – 1 )
0000000000000000 0000011111111111 &
0000000000000000 0000011111111110
————————————————–
0000000000000000 0000011111111110
count = 1

1022 & ( 1022 – 1 )
0000000000000000 0000011111111110 &
0000000000000000 0000011111111100
————————————————–
0000000000000000 0000011111111100
count = 2

1020 & ( 1020 – 1 )
0000000000000000 0000011111111100 &
0000000000000000 0000011111111011
————————————————–
0000000000000000 0000011111111000
count = 3

1015 & ( 1015 – 1)
0000000000000000 0000011111111000 &
0000000000000000 0000011111110111
————————————————–
0000000000000000 0000011111110000
count = 4
.
.
.

512 & ( 512 – 1 )
0000000000000000 0000010000000000 &
0000000000000000 0000001111111111
—————————————————–
0000000000000000 0000000000000000
count = 10

Source code:

/* Written by Giri
   A function that implements the Hamming  weight of a binary 
   vector 
   In this example, I have used a built in function called 
   int __builtin_popcount (unsigned int x), which will return 
   the number of non-zero values in the given unsigned int */

#include "header.h"

int main () {
	ulong u;
	int choice;
	do {
		printf ("1. Find the Hamming weight of a binary vector (using built in function): \n");
		printf ("2. Find the Hamming weight of a binary vector (using a custom function): \n");
		printf ("3. Exit\n");
		printf ("Enter your choice: ");
		scanf ("%d", &choice);
		switch ( choice ) {
			case 1: printf ("Enter the binary vector: ");
					scanf ("%lu", &u);
					printf ("The Number of 1s in your binary vector is : %d\n", __builtin_popcount(u));
			break;

			case 2: printf ("Enter the binary vector: ");
					scanf ("%lu", &u);
					if ( u == 0 )
						printf ("There isn't any non-zero values in your binary vector\n");
					else
						printf ("The Number of 1s in your binary vector is : %lu\n", hamming_weight(u));
			break;

			case 3: 
				exit(0);
			break;

			default:
			break;
		}
	} while ( ! ( choice  2 ) );
	return  0;
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s