Longest Consecutive Sequence of 1’s in the Binary Representation of a Number

Introduction

The problem discussed in this blog is elementary if you have a little knowledge about Bit Manipulation in C++.

OHH!! So you just started coding, and I am telling you to know about Bit Manipulation. MY BAD :( 

Don’t worry; I’ll explain each concept in this blog before implementing it in code. So you can relax now.

Now, let’s discuss our problem!

In this question, we are given a number (any integer), and we are asked to find the length of the longest consecutive 1’s in the binary representation of that number.

Let’s see this in detail.

In the Binary Representation of a number, we represent the number in bits that are either 0’s or 1’s. There are 8 bits in a byte, and in C++, an integer takes up 4 bytes, so there are 31 bits for an integer in C++ (ignoring one signed bit). So the maximum number that is represented as 1111111111111111111111111111111, which is 2147483647.

Coming to our question, if we take the INT_MAX as input, then we’ll get answer 31 because there are 31 consecutive 1’s in the binary representation of 2147483647.

Before jumping to the algorithm, we’ll look at some Bitwise operators:

• & (AND) OPERATOR - It returns true if both bits are 1 and false otherwise.

Example: 1011 & 0110 = 0010 (because only 3rd bit is 1 in both numbers)

• << LEFT SHIFT - It is used to shift the binary number by specified bits.

Example: 0101<<1 = 1010 (all the bits are shifted one place to the left and last-place is filled with 0)

Now that we have understood the question and the related concepts, let’s formulate an algorithm to code this question.

Also see, Euclid GCD Algorithm

Algorithm Description

The idea to solve this problem is very interesting. Although, you will have to remember this for the future.

The idea says that if we take a number and apply AND (&) operation with our original number left-shifted by 1, we’re decrementing all the sequences of 1’s in the original number by 1.

Let’s clear the clutter with an example.

If I take a number n = 2974, the binary representation of this number is 101110011110.

Here we can see that the longest sequence of 1’s is 4. Also, there are three 1’s sequences of different lengths 1, 3, and 4.

Left shifting the number by 1, 101110011110<<1 = 011100111100

Next, performing the AND (&) operation of the newly formed number with the original number,

101110011110 & 011100111100 = 001100011100

If we observe the result, we’ll see that all three sequences of 1’s are decremented by 1. The first sequence, which was earlier of length 1, got reduced to 0, the third sequence got reduced to 2, and the third sequence got reduced to 3 from 4 length.

Again, the idea here is to get the longest sequence by performing the above steps until the number becomes zero.

In the next iteration, we’ll get 001100011100 & 011000111000 = 001000011000

Further iterating, 001000011000 & 010000110000 = 000000010000

In the last step, our number becomes zero, so we’ll stop, 000000010000 & 000000100000 = 000000000000

It took four iterations to get the longest sequence to complete 0. Hence, four will be our answer.