Count total bits in a number
Given a positive number n, count total bit in it.
Examples:
Input : 13 Output : 4 Binary representation of 13 is 1101 Input : 183 Output : 8 Input : 4096 Output : 13
Method 1 (Using Log)
The log2(n) logarithm in base 2 of n, which is the exponent to which 2 is raised to get n only integer and we add 1 find total bit in a number in log(n) time.
C++
// C++ program to find total bit in given number #include <iostream> #include <cmath> unsigned countBits(unsigned int number) { // log function in base 2 // take only integer part return ( int )log2(number)+1; } // Driven program int main() { unsigned int num = 65; std::cout<<countBits(num)<< '\n' ; return 0; } // This code is contributed by thedev05. |
C
// C program to find total bit in given number #include <stdio.h> #include <math.h> unsigned countBits(unsigned int number) { // log function in base 2 // take only integer part return ( int )log2(number)+1; } // Driven program int main() { unsigned int num = 65; printf ( "%d\n" , countBits(num)); return 0; } |
Java
// Java program to // find total bit // in given number import java.io.*; class GFG { static int countBits( int number) { // log function in base 2 // take only integer part return ( int )(Math.log(number) / Math.log( 2 ) + 1 ); } // Driver code public static void main (String[] args) { int num = 65 ; System.out.println(countBits(num)); } } // This code is contributed by vij |
Python3
# Python3 program to find # total bit in given number import math def countBits(number): # log function in base 2 # take only integer part return int ((math.log(number) / math.log( 2 )) + 1 ); # Driver Code num = 65 ; print (countBits(num)); # This code is contributed by mits |
C#
// C# program to find total bit // in given number using System; class GFG { static uint countBits( uint number) { // log function in base 2 // take only integer part return ( uint )Math.Log(number , 2.0) + 1; } // Driver code public static void Main() { uint num = 65; Console.WriteLine(countBits(num)); } } // This code is contributed by Sam007. |
PHP
<?php // PHP program to find total // bit in given number function countBits( $number ) { // log function in base 2 // take only integer part return (int)(log( $number ) / log(2)) + 1; } // Driver Code $num = 65; echo (countBits( $num )); // This code is contributed by Ajit. ?> |
Javascript
<script> // JavaScript program to find total bit in given number function countBits(number) { // log function in base 2 // take only integer part return Math.floor(Math.log2(number)+1); } // Driven program let num = 65; document.write(countBits(num)); // This code is contributed by Surbhi Tyagi </script> |
Output
7
Time Complexity : O(logn)
Auxiliary Space : O(1)
Method 2 (Using Bit Traversal)
C
/* Function to get no of bits in binary representation of positive integer */ #include <stdio.h> unsigned int countBits(unsigned int n) { unsigned int count = 0; while (n) { count++; n >>= 1; } return count; } /* Driver program*/ int main() { int i = 65; printf ( "%d" , countBits(i)); return 0; } |
Java
/* Function to get no of bits in binary representation of positive integer */ class GFG { static int countBits( int n) { int count = 0 ; while (n != 0 ) { count++; n >>= 1 ; } return count; } /* Driver program*/ public static void main(String[] arg) { int i = 65 ; System.out.print(countBits(i)); } } // This code is contributed by Smitha. |
Python3
C#
PHP
Javascript
Output
7
Time Complexity : O(logn)
Auxiliary Space : O(1)
Method 3 ( Using conversion from binary to string)
C++
// C++ program to implement the approach #include <bits/stdc++.h> using namespace std; // function to count the number of bits in a number n int count_bits( int n) { // to_string() returns the binary string // representation of the number n string binary = bitset< 64 >(n).to_string(); // returning the length of the binary string return 64 - binary.find( '1' ); } int main() { int a = 65; int b = 183; cout << "Total bits in " << a << " : " << count_bits(a) << endl; cout << "Total bits in " << b << " : " << count_bits(b) << endl; } // This code is contributed by phasing17 |
Java
// Java code to implement the approach class GFG { // function to count the number of bits in a number n static int count_bits( int n) { // return the length of the binary string return Integer.toBinaryString(n).length(); } // Driver Code public static void main(String[] args) { int a = 65 ; int b = 183 ; // function call System.out.printf( "Total bits in %d: %d\n" , a, count_bits(a)); System.out.printf( "Total bits in %d: %d\n" , b, count_bits(b)); } } // this code is contributed by phasing17 |
Python3
C#
Javascript
// JavaScript program to implement the approach // function to count the number of bits in a number n function count_bits(n) { // toString(2) returns the binary string // representation of the number n let binary = n.toString(2); // returning the length of the binary string return binary.length; } let a = 65; let b = 183; console.log( "Total bits in" , a, ":" , count_bits(a)); console.log( "Total bits in" , b, ":" , count_bits(b)); // This code is contributed by phasing17 |
Output
Total bits : 7 Total bits : 8
Time Complexity : O(logn)
Auxiliary Space : O(1)