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
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.
using namespace std;
// Function to calculate longest consecutive 1's in the binary representation of the number
int longestConsecutiveOnes(int n)
// Initializing a count variable to store the consecutive ones
int result = 0;
// We'll keep iterating till our original number becomes 0
// x variable stores the original number left-shifted by 1
int x = n<<1;
// Taking AND operation and storing the result in n
n = n & x;
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
The time complexity to find the maximum number of consecutive 1’s in the binary representation of the number is O(k), where k is the longest sequence of 1’s.
Even in the worst case, the loop will not run more than 31 times for integer values.
The space complexity to find the maximum number of consecutive 1’s in the binary representation of the number is constant O(1) because no extra space is being used.
Check out this problem - Shortest Common Supersequence.
Must read decimal to binary c++
Frequently Asked Questions
What is the largest and the smallest value of an integer in C++?
Answer: INT_MAX denotes the largest integer value in C++, and INT_MIN represents the smallest integer value.
- The value of INT_MAX is 2147483647 and
- The value of INT_MIN is -2147483648.
What is the worst-case time complexity to find the longest consecutive sequence of 1’s in the Binary Representation of a number?
Answer: O(k), where k is the maximum number of consecutive 1’s in the binary number.
In the worst-case scenario, we’ll get INT_MAX which contains 31 consecutive 1’s. Hence, in the worst-case, the loop will execute 31 times.
What is the difference between AND operation and OR operation?
Answer: The AND (&) operator returns true when both the operands are true and returns false otherwise, whereas the OR (|) operator returns true when both operands are true.
What are the bitwise operators in C++?
Answer: The bitwise operators perform operations on the bit level.
In C++, there are six bitwise operators: AND (&), OR (|), XOR (^), LEFT-SHIFT (<<), RIGHT-SHIFT (>>), and NOT (~).
What is an unsigned int in C++?
Answer: The unsigned int is used to store 32-bit integers in C++. In signed numbers, we reserve one bit for positive and negative values, but since that bit is not present here, the value of an unsigned integer is always greater than or equal to zero.
The maximum value of the integer that we can store in unsigned int is 4294967295.
In this blog post, we discussed a simple bit manipulation problem. The problem can be easily solved using the idea discussed above. It is important to remember this idea for the future as it can be applied to many similar problems. We also discussed some bitwise operators and how they are used.
Bit manipulation is a very crucial topic from the interview’s point of view. Hence, you should be aware of these problems and the techniques to solve them.
Read about Bitwise Operators in C here.
Thank you so much for your time. Keep Learning, Keep growing!!