Comparing leading zeros in binary representations of two numbers

0 0 5 minutes read

Given two integer numbers x and y. Compare and print which one of them has more leading zeros using Bitwise operation. If both the no. have the same no. of leading zeros, print “Equal”.
Note:- A leading zero is any 0 digit that comes before the first nonzero digit in the binary notation of the number.
Examples:

Input : 10, 16
Output :10
Explanation: If we represent the no.s using 8 bit only then 
Binary(10) = 00001010
Binary(16) = 00010000
Clearly, 10 has 4 leading zeros and 16 has 3 leading zeros
Input : 10, 12
Output : Equal
Binary(10) = 00001010
Binary(12) = 00001100
Both have equal no. of leading zeros.

Solution 1: The Naive approach is to first find the binary representation of the numbers and then count the no. of leading zeros.
Solution 2: Find largest power of twos smaller than given numbers, and compare these powers of twos to decide answer.
Solution 3: An efficient approach is to bitwise XOR and AND operators.

Case 1: If both have same no. of leading zeros then (x^y) <= (x & y) because same number of leading 0s would cause a 1 at higher position in x & y.
Case 2 : If we do negation of y and do bitwise AND with x, we get a one at higher position than in y when y has more number of leading 0s.
Case 3: Else x has more leading zeros

C++

// CPP program to find the number with more
// leading zeroes.
#include <bits/stdc++.h>
using namespace std;
 
// Function to compare the no. of leading zeros
void LeadingZeros(int x, int y)
{
    // if both have same no. of leading zeros
    if ((x ^ y) <= (x & y)) 
        cout << "\nEqual";
 
    // if y has more leading zeros
    else if ((x & (~y)) > y) 
        cout << y;
 
    else
        cout << x;
}
 
// Main Function
int main()
{
    int x = 10, y = 16;
    LeadingZeros(x, y);
    return 0;
}

Java

// Java program to find the number 
// with more leading zeroes. 
class GFG
{
// Function to compare the no. 
// of leading zeros 
static void LeadingZeros(int x, int y) 
{ 
    // if both have same no. of 
    // leading zeros 
    if ((x ^ y) <= (x & y)) 
        System.out.print("\nEqual");
 
    // if y has more leading zeros 
    else if ((x & (~y)) > y) 
        System.out.print(y); 
 
    else
        System.out.print(x); 
} 
 
// Driver Code
public static void main (String[] args) 
{
    int x = 10, y = 16; 
    LeadingZeros(x, y); 
}
} 
 
// This code is contributed by Smitha

Python3

# Python 3 program to find the number 
# with more leading zeroes.
 
# Function to compare the no. of
# leading zeros
def LeadingZeros(x, y):
     
    # if both have same no. of
    # leading zeros
    if ((x ^ y) <= (x & y)): 
        print("Equal")
 
    # if y has more leading zeros
    elif ((x & (~y)) > y) :
        print(y)
 
    else:
        print(x)
 
# Driver Code
if __name__ == '__main__':
    x = 10
    y = 16
    LeadingZeros(x, y)
 
# This code is contributed 
# by Surendra_Gangwar

C#

// C# program to find the number 
// with more leading zeroes. 
using System;
 
class GFG
{
// Function to compare the no. 
// of leading zeros 
static void LeadingZeros(int x, int y) 
{ 
    // if both have same no. of 
    // leading zeros 
    if ((x ^ y) <= (x & y)) 
        Console.WriteLine("\nEqual"); 
 
    // if y has more leading zeros 
    else if ((x & (~y)) > y) 
        Console.WriteLine(y); 
 
    else
        Console.WriteLine(x); 
} 
 
// Driver Code 
static public void Main ()
{
    int x = 10, y = 16; 
    LeadingZeros(x, y); 
}
} 
 
// This code is contributed by ajit

Javascript

<script>
 
// Javascript program to find the number with more
// leading zeroes.
 
// Function to compare the no. of leading zeros
function LeadingZeros(x, y)
{
    // if both have same no. of leading zeros
    if ((x ^ y) <= (x & y)) 
        document.write("<br>Equal");
 
    // if y has more leading zeros
    else if ((x & (~y)) > y) 
        document.write(y);
 
    else
        document.write(x);
}
 
// Main Function
    let x = 10, y = 16;
    LeadingZeros(x, y);
 
</script>

PHP

<?php
// PHP program to find the number
// with more leading zeroes.
 
// Function to compare the no.
// of leading zeros
function LeadingZeros($x, $y)
{
    // if both have same no. of
    // leading zeros
    if (($x ^ $y) <= ($x & $y)) 
        echo "\nEqual";
 
    // if y has more leading zeros
    else if (($x & (~$y)) > $y) 
        echo $y;
 
    else
        echo $x;
}
 
// Driver Code
$x = 10;
$y = 16;
LeadingZeros($x, $y);
     
// This code is contributed by ajit
?>

Output

Time Complexity: O(1)
Space Complexity: O(1)

Approach#2: Using format

Take two integer inputs from the user. Convert the input numbers to 8-bit binary strings using the format() function. Count the number of leading zeros in each binary string using the lstrip() and len() functions. Compare the number of leading zeros of the two binary strings. Print the number which has more leading zeros, or a message saying that both numbers have equal number of leading zeros.

Algorithm

1. Read the two integers num1 and num2 from the user.
2. Convert num1 and num2 to 8-bit binary strings using the format() function.
3. Count the number of leading zeros in bin1 and bin2 using the lstrip() and len() functions.
4. Compare leading_zeros1 and leading_zeros2.
5. If leading_zeros1 is greater than leading_zeros2, print num1 has more leading zeros.
6. If leading_zeros2 is greater than leading_zeros1, print num2 has more leading zeros.
7. If leading_zeros1 is equal to leading_zeros2, print both numbers have equal number of leading zeros.

C++

#include <iostream>
#include <string>
#include <bitset>
 
int main() {
    int num1 = 10;
    int num2 = 12;
 
    // Convert num1 and num2 to 8-bit binary strings
    std::string bin1 = std::bitset<8>(num1).to_string();
    std::string bin2 = std::bitset<8>(num2).to_string();
 
    // Count leading zeros in the binary strings
    int leading_zeros1 = bin1.find_first_not_of('0');
    int leading_zeros2 = bin2.find_first_not_of('0');
 
    // Compare the counts of leading zeros and print the result
    if (leading_zeros1 == leading_zeros2) {
        std::cout << "Equal" << std::endl;
    } else if (leading_zeros1 < leading_zeros2) {
        std::cout << num1 << " has fewer leading zeros." << std::endl;
    } else {
        std::cout << num2 << " has fewer leading zeros." << std::endl;
    }
 
    return 0;
}

Python3

num1 = 10
num2 = 12
 
bin1 = format(num1, '08b') # convert to 8-bit binary string
bin2 = format(num2, '08b')
 
leading_zeros1 = len(bin1) - len(bin1.lstrip('0'))
leading_zeros2 = len(bin2) - len(bin2.lstrip('0'))
 
if leading_zeros1 > leading_zeros2:
    print(num1)
elif leading_zeros2 > leading_zeros1:
    print(num2)
else:
    print("Equal")

Output

Equal

Time Complexity: O(1) because the program executes a fixed number of instructions regardless of the input values. The execution time of the program is constant and does not depend on the input size.

Space Complexity: O(1) because the program uses a fixed amount of memory to store the input variables, binary strings, and variables to count the leading zeros. The amount of memory used by the program does not depend on the input size.

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 zambiatek!