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 * 2^b)

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).