Count number of trailing zeros in Binary representation of a number using Bitset
Given a number. The task is to count the number of Trailing Zero in Binary representation of a number using bitset.
Examples:
Input : N = 16
Output : 4
Binary representation of N is 10000. Therefore,
number of zeroes at the end is 4.
Input : N = 8
Output : 3
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach: We simply set the number in the bitset and then we iterate from 0 indexes of bitset, as soon as we get 1 we will break the loop because there is no trailing zero after that.
Below is the implementation of above approach:
C++
// C++ program to count number of trailing zeros // in Binary representation of a number // using Bitset #include <bits/stdc++.h> using namespace std; // Function to count number of trailing zeros in // Binary representation of a number // using Bitset int CountTrailingZeros( int n) { // declare bitset of 64 bits bitset<64> bit; // set bitset with the value bit |= n; int zero = 0; for ( int i = 0; i < 64; i++) { if (bit[i] == 0) zero++; // if '1' comes then break else break ; } return zero; } // Driver Code int main() { int n = 4; int ans = CountTrailingZeros(n); cout << ans << "\n" ; return 0; } |
Java
// Java program to count number of trailing zeros // in Binary representation of a number // using Bitset import java.util.*; import java.lang.*; import java.io.*; class GFG { // Function to count number of trailing zeros in // Binary representation of a number // using Bitset static int CountTrailingZeros( int n) { String bit = Integer.toBinaryString(n); StringBuilder bit1 = new StringBuilder(); bit1.append(bit); bit1=bit1.reverse(); int zero = 0 ; for ( int i = 0 ; i < 64 ; i++) { if (bit1.charAt(i) == '0' ) zero++; // if '1' comes then break else break ; } return zero; } // Driver Code public static void main(String []args) { int n = 4 ; int ans = CountTrailingZeros(n); System.out.println(ans); } } // This code is contributed by chitranayal |
Python3
# Python3 program to count # number of trailing zeros in # Binary representation of a number # Function to count number of # trailing zeros in Binary # representation of a number def CountTrailingZeros(n): # declare bitset of 64 bits bit = bin (n)[ 2 :] bit = bit[:: - 1 ] zero = 0 ; for i in range ( len (bit)): if (bit[i] = = '0' ): zero + = 1 # if '1' comes then break else : break return zero # Driver Code n = 4 ans = CountTrailingZeros(n) print (ans) # This code is contributed # by Mohit Kumar |
C#
// C# program to count number of trailing zeros // in Binary representation of a number // using Bitset using System; class GFG { // Function to count number of trailing zeros in // Binary representation of a number // using Bitset static int CountTrailingZeros( int n) { string bit=Convert.ToString(n, 2); char [] charArray = bit.ToCharArray(); Array.Reverse( charArray ); string bit1 = new string ( charArray ); int zero = 0; for ( int i = 0; i < 64; i++) { if (bit1[i] == '0' ) { zero++; } // if '1' comes then break else { break ; } } return zero; } // Driver Code static public void Main () { int n = 4; int ans = CountTrailingZeros(n); Console.WriteLine(ans); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // JavaScript program to count number of trailing zeros // in Binary representation of a number // using Bitset // Function to count number of trailing zeros in // Binary representation of a number // using Bitset function CountTrailingZeros(n) { let bit = n.toString(2); let bit1=bit.split( "" ); bit1=bit1.reverse(); let zero = 0; for (let i = 0; i < 64; i++) { if (bit1[i] == '0' ) zero++; // if '1' comes then break else break ; } return zero; } // Driver Code let n = 4; let ans = CountTrailingZeros(n); document.write(ans); // This code is contributed by rag2127 </script> |
Output
2
Time Complexity: O(1)
Auxiliary Space: O(1)
Approach: Bitwise Operation
- To count the number of trailing zeroes in the binary representation of a number using bitwise operations.
- We can repeatedly right-shift the number by 1 until the least significant bit (LSB) becomes 1.
- The number of right shifts performed will give us the count of trailing zeroes.
Below is the implementation of above approach:
C++
#include <iostream> using namespace std; int count_trailing_zeroes( int n) { int count = 0; while ((n & 1) == 0) { count += 1; n >>= 1; } return count; } int main() { int n1 = 16; cout << count_trailing_zeroes(n1) << endl; return 0; } |
Java
import java.util.Scanner; public class GFG { // Function to count trailing zeroes in a number static int countTrailingZeroes( int n) { int count = 0 ; while ((n & 1 ) == 0 ) { count += 1 ; n >>= 1 ; } return count; } // Driver Code public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print( "Enter an integer: " ); int n1 = 16 ; System.out.println( "Number of trailing zeroes: " + countTrailingZeroes(n1)); } } |
Python
# Python program to count # number of trailing zeros in # Binary representation of a number def count_trailing_zeroes(n): count = 0 while n & 1 = = 0 : count + = 1 n >> = 1 return count # Driver Code n1 = 16 print (count_trailing_zeroes(n1)) |
C#
using System; namespace CountTrailingZeroes { class Program { // Function to count trailing zeroes in a number static int CountTrailingZeroes( int n) { int count = 0; while ((n & 1) == 0) { count += 1; n >>= 1; } return count; } static void Main( string [] args) { int n1 = 16; Console.WriteLine(CountTrailingZeroes(n1)); } } } |
Javascript
function countTrailingZeroes(n) { let count = 0; while ((n & 1) === 0) { count += 1; n >>= 1; } return count; } // Example usage const n1 = 16; console.log(countTrailingZeroes(n1)); |
Output
4
Time Complexity: O(log N), where N is the value of the input number n.
Auxiliary Space: O(1)
Contact Us