CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6
  1. #1
    Join Date
    May 2015
    Posts
    500

    Number of leading zeros in binary representation of a number

    Hello,

    I was trying solve the above problem. I came across a solution in the google:

    Code:
    // C++ program of number of leading zeros in
    // binary representation of a given number
    #include <bits/stdc++.h>
    using namespace std;
     
    // Function to count the no. of leading zeros
    int countZeros(unsigned int x)
    {
        // Keep shifting x by one until leftmost bit
        // does not become 1.
        int total_bits = sizeof(x) * 8;
        int res = 0;
        while ( !(x & (1 << (total_bits - 1))) )
        {
            x = (x << 1);
            res++;
        }
     
        return res;
    }
     
    // Main function
    int main()
    {
        int x = 101;
        cout << countZeros(x);
        return 0;
    }
    as you can see int variable x in main is cast implicitly to unsigned int. "casting" is platform dependent , will it cause issues.
    If I pass negetive number to x, the cast value might be represented as 2s complement of the number. (or whatever format the underlying platform is using and also "bigendian/little endian" might also affect the binary rep. Am i right ? Please kindly comment

    I was asked the above Q quite sometime back and just wondering about it yesterday

    thanks
    Pdk

  2. #2
    Join Date
    May 2015
    Posts
    500

    Re: Number of leading zeros in binary representation of a number

    Also i found an issue, if i pass "0", the while is infinite loop. May be for loop till the number of bits is better (which breaks, if "1" is encountered)

  3. #3
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Number of leading zeros in binary representation of a number

    Yes. There is a flaw in the logic. There's at least a couple of different ways to fix the code. I'll leave this as an exercise...

    If I pass negetive number to x,
    Then there will be no zeroes to the left as a negative number has 1 as the left most bit. C++20 specifies 2-complement for signed numbers.

    When doing right shifts (>>), for a signed type it will duplicate the left-most-bit when shifting (sign extension). So for a negative value 1 will be shifted in and if 0 then 0 will be shifted in. If a 0 is always required to be shifted in with a right shift, then the type needs to be unsigned.

    From where did this solution come - geeks for geeks perhaps?? #include <bits... isn't now valid!

    Using 'modern' C++ then perhaps:

    Code:
    #include <iostream>
    #include <bitset>
    #include <concepts>
    #include <climits>
    
    auto countZeros(std::integral auto x) {
    	const std::bitset<sizeof x * CHAR_BIT> bits(x);
    	size_t cnt {};
    
    	for (size_t i { bits.size() }; i && !bits[i - 1]; --i, ++cnt);
    	return cnt;
    }
    
    int main() {
    	std::cout << countZeros(101);
    }
    Last edited by 2kaud; February 21st, 2023 at 04:21 AM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  4. #4
    Join Date
    May 2015
    Posts
    500

    Re: Number of leading zeros in binary representation of a number

    Thankyou very much kaud for the reply and inputs . Helped me a lot.

    Yes, i found that solution is geeksforgeeks.

    Thankyou very much for the nice solution. We currently moved to visual studio 22, but not using those new features provided by the compiler.

  5. #5
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Number of leading zeros in binary representation of a number

    Note that not everything re C++ you find on the internet is good code or even correct! Much has been present for aeons and relates to C++ as it was many, many years ago as opposed to modern C++.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  6. #6
    Join Date
    May 2015
    Posts
    500

    Re: Number of leading zeros in binary representation of a number

    Thankyou Kaud, yes ie why I asked here, as I know this may be trivial. But you and this forum, just not solves them, and helps with lot of info.
    Thanks a lot again for your time and patience

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured