Given an integer N, the task is to find the number of trailing zeroes in the binary representation of the given number.
Examples:
Input: N = 12
Output: 2
Explanation:
The binary representation of the number 13 is “1100”.
Therefore, there are two trailing zeros in the 12.Input: N = -56
Output: 3
Explanation:
The binary representation of the number -56 is “001000”.
Therefore, there are 3 trailing zeros present in -56.
Approach: Follow the steps to solve the problem
- The idea is to use the observation that after calculating XOR of N with N – 1, all the set bit of N left to the rightmost set bit, i.e LSB set bit disappears and the rightmost set bit of N becomes the leftmost set bit of N ^ (N – 1).
- Print the count of bits of a number (N ^ (N – 1)) decremented by 1.
Below is the implementation of the above approach:
C++
// C++ implementation// of the above approach#include <bits/stdc++.h>using namespace std;// Function to print count of// trailing zeroes present in// binary representation of Nint countTrailingZeroes(int N){ // Count set bits in (N ^ (N - 1)) int res = log2(N ^ (N - 1)); // If res < 0, return 0 return res >= 0 ? res : 0;}// Driver Codeint main(){ int N = 12; // Function call to print the count // of trailing zeroes in the binary // representation of N cout << countTrailingZeroes(N); return 0;} |
Java
// Java implementation// of the above approachimport java.io.*;class GFG { // Function to print count of // trailing zeroes present in // binary representation of N public static int countTrailingZeroes(int N) { // Stores XOR of N and (N-1) int res = N ^ (N - 1); // Return count of set bits in res return (int)(Math.log(temp) / Math.log(2)); } // Driver Code public static void main(String[] args) { int N = 12; // Function call to print the count // of trailing zeroes in the binary // representation of N System.out.println( countTrailingZeroes(N)); }} |
Python3
# Python3 implementation# of the above approachfrom math import log2# Function to print count of# trailing zeroes present in# binary representation of Ndef countTrailingZeroes(N): # Count set bits in (N ^ (N - 1)) res = int(log2(N ^ (N - 1))) # If res < 0, return 0 return res if res >= 0 else 0# Driver Codeif __name__ == '__main__': N = 12 # Function call to print the count # of trailing zeroes in the binary # representation of N print (countTrailingZeroes(N)) # This code is contributed by mohit kumar 29. |
C#
// C# implementation// of the above approachusing System;public class GFG{ // Function to print count of // trailing zeroes present in // binary representation of N public static int countTrailingZeroes(int N) { // Stores XOR of N and (N-1) int res = (int)Math.Log(N ^ (N - 1), 2.0); // Return count of set bits in res if(res >= 0) return res; else return 0; } // Driver Code static public void Main () { int N = 12; // Function call to print the count // of trailing zeroes in the binary // representation of N Console.WriteLine( countTrailingZeroes(N)); }}// This code is contributed by Dharanendra L V. |
Javascript
<script>// Javascript implementation// of the above approach// Function to print count of// trailing zeroes present in// binary representation of Nfunction countTrailingZeroes(N){ // Count set bits in (N ^ (N - 1)) let res = parseInt(Math.log(N ^ (N - 1)) / Math.log(2)); // If res < 0, return 0 return res >= 0 ? res : 0;}// Driver Codelet N = 12;// Function call to print the count// of trailing zeroes in the binary// representation of Ndocument.write(countTrailingZeroes(N));// This code is contributed by souravmahato348 </script> |
Output:
2
Time Complexity: O(log(N))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
