## Introduction

This article aims to familiarise you with the bitwise operator problems and the concept of Least Significant Bit.

To brush up on your knowledge of bitwise operators, you can read the article __Bitwise Operators__ on Coding Ninjas Studio.

Letâ€™s see the problem statement in the next section.

## Problem Statement

An array consisting of N positive integers is given.

Find the maximum sum of Least Significant Bit of Bitwise OR of all possible N/2 pairs from the given array, i.e. arrange the elements of the array into N/2 elements to maximise the sum of the Least Significant Bit of the Bitwise OR of the N/2 pairs.

Before moving on to the examples, it's important to understand what does least significant bit imply as we will use this concept to build up the solution approach.

**Note**: Throughout this article, we will be using the term â€ślsbâ€ť which is a short form for Least Significant Bit.

**Least significant bit**

The least significant bit is the value of the number when all the set bits other than the rightmost bit in the binary representation of the number is set to 0.

It can also be defined as the largest 2^{x}(2 raised to x where x is non-negative integers) that divides the number.

Consider a few examples below:

**1. Number = 10**

The binary representation of 10 is 1010. So when only the rightmost set bit is kept in 1010 we get 0010 i.e. 2. So the lsb of 10 is 2.

We can also see that 2^{0}=1 and 2^{1}=2 divide 10 but not 2^{2}=4. So the answer is 2^{1} i.e. 2

**2. Number = 28**

The binary representation of 28 is 11100. So when only the rightmost set bit is kept in 11100 we get 00100 i.e. 4. So the lsb of 28 is 4.

We can alternatively see that 4 i.e. 2^{2} divides 28 but 2^{3}=8 does not divide 28. So the answer is 2 raised to 2 i.e. 4.

**3. Number = 15**

The binary representation of 15 is 1111. So when only the rightmost set bit is kept in 1111 we get 0001 i.e. 1. So lsb of 15 is 1.

Now, let us see a few of the examples of the problem statement:

**1. arr=[3,5,7,10,11,16]**

Output: 4

Explanation: LSB(least significant bit) of 3,5,7,10,11,16 are 1,1,1,2,1,16 respectively.

So making the pairs (16,10), (11,7) and (5,3), the bitwise OR is 26, 15 and 7, respectively. Thus the Least Significant Bits are 2, 1 and 1, respectively. Thus the sum is 4.

**2. arr=[2,3]**

Output: 1

Explanation: Only one pair can be formed, i.e. (2,3). The bitwise OR is 3, and its lsb is 1. So the answer is 1.

Also see, __Euclid GCD Algorithm__