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;