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;