Find the Bit Length of a Number

In this lesson, we use the Left Shift operator to find the bit length of a number.

Introduction

In this question, we take input and find its bit length.

Problem Statement

Given an input, find its bit length.

``````Input: 8

Output: 4 (1000)``````
``````Input: 2

Output: 2 (10)``````
``````Input: 7

Output: 3 (111)``````

Algorithm

We already discussed the formula of the left shift operator.

a << b = (a * 2b)

Steps:

• Initialize a variable `bitsCounter` with value `0`.
• Now, left-shift `bitsCounter` until its value is less or equal to the given number.
• if `true`, increament the `bitsCounter` on each iteration.
• else, return `bitsCounter`.

Solution

Java

``````class BitLength {
static int bitsLength(int number) {
int bitsCounter = 0;

while ((1 << bitsCounter) <= number) {
bitsCounter += 1;
}
return bitsCounter;
}

public static void main(String[] args) {
System.out.println(bitsLength(8));
System.out.println(bitsLength(2));
System.out.println(bitsLength(7));
}
}``````

Python

``````def bitsLength(n):
bitsCounter = 0

while((1 << bitsCounter) <= n):
bitsCounter += 1

return bitsCounter

print(bitsLength(8))
print(bitsLength(2))
print(bitsLength(7))
``````

JavaScript

``````/**
* Return the number of bits used in the binary representation of the number.
*
* @param {number} number
* @return {number}
*/
const bitLength = (number) => {
let bitsCounter = 0;

while ((1 << bitsCounter) <= number) {
bitsCounter += 1;
}

return bitsCounter;
}

console.log(bitLength(8));
console.log(bitLength(2));
console.log(bitLength(7));

``````

C++

``````#include <iostream>
using namespace std;

int bitsLength(int n){
int bitsCounter = 0;

while((1 << bitsCounter) <= n){
bitsCounter += 1;
}

return bitsCounter;
}

int main() {
cout << bitsLength(8) << "\n";
cout << bitsLength(2) << "\n";
cout << bitsLength(7);
return 0;
}``````

TypeScript

``````/**
* Return the number of bits used in the binary representation of the number.
*
* @param {number} number
* @return {number}
*/
export const bitLength = (number: number): number => {
let bitsCounter: number = 0;

while ((1 << bitsCounter) <= number) {
bitsCounter += 1;
}

return bitsCounter;
}

console.log(bitLength(8));
console.log(bitLength(2));
console.log(bitLength(7));

``````

Complexity analysis

Time Complexity

We are running a loop, which continues until and unless the loop breaks. The inputs never change. overall, its `O``(``n``)`.

Space Complexity

We didn’t create an extra memory for this. So, the space complexity is `O(1)`.

Coding Interview QuestionsData Structures and AlgorithmsBit Manipulation

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

Bit Manipulation Course Overview

Overview In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies. To kick things