We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Bit Manipulation
  4. 2's complement
  5. Discussions

2's complement

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 38 Discussions, By:

votes

Please Login in order to post a comment

  • ayushr2
    4 years ago+ 6 comments

    For all those looking for an explanation, here are some clues for a O(1) solution:

    Lets break down the problem into finding out the 1s in all binary representation of numbers from 0 to n if n is positive and n to -1 if n is negative.

    Lets look at positive numbers. Lets take n = 10. Here is the binary representation of 0 - 10.

    0000
    0001
    0010
    0011
    0100
    0101
    0110
    0111
    1000
    1001
    1010
    

    Look at it column by column. Do you see a pattern? The right extreme least significant bit is 1 alternatively. so for height of column h = n + 1, 1 will be repeated h / 2 times. Now for second column, pattern is 0011. so for column two 1 will be repeated (h / 4)*2 + max(0, (h % 4) - 2) times. Can you generate a formula? we just need to do it for all 32 bits and boom we have the answer!

    Now look at negative numbers. let n = -8. Here are the binary representation from -1 to -8:

    1111
    1110
    1101
    1100
    1011
    1010
    1001
    1000
    

    Can you figure out a similar pattern? this series differs from before only in the fact that hieght will be h = abs(n) and now in every recurring pattern 1 comes before 0. For first column its 1010 and second column its 1100 instead of 0011. Can you come up with another formula?

    Assuming you have cracked both the formula, the problem reduces to this:

    a, b = map(int, input().split())
        if a < 0 and b < 0:
            print(get_one_count_negative(a) - get_one_count_negative(b + 1))
        elif a < 0 and b >= 0:
            print(get_one_count_negative(a) + get_one_count_positive(b))
        elif a == 0:
            print(get_one_count_positive(b))
        else:
            print(get_one_count_positive(b) - get_one_count_positive(a - 1))
    

    Happy Coding!

    19|
    Permalink
    View more Comments..
  • AbhijeetMuneshwr
    6 years ago+ 0 comments

    I think this link will help.

    http://stackoverflow.com/questions/7942732/number-of-1s-in-the-twos-complement-binary-representations-of-integers-in-a-ran

    3|
    Permalink
  • alfonso_csrz
    1 year ago+ 0 comments

    https://www.youtube.com/watch?v=4qH4unVtJkE If someone is interested

    1|
    Permalink
  • madhu43_engg
    5 years ago+ 1 comment

    can anyone explain this. I couldn't get any idea

    1|
    Permalink
  • ntcong
    9 years ago+ 2 comments

    I'm using go and only have 8s to count. I used a fast bit counting which takes only 2ns to count a single number, but for the whole list it slows a lot. How's everyone approach to this problem ? I know we can't count number by number but I can't find any viable ideal

    1|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature