c# - What does binary representation of uint is like?

Question

I'm trying to solve a simple question on leetcode.com (https://leetcode.com/problems/number-of-1-bits/) and I encounter a strange behavior which is probably my lack of understanding...

My solution to the question in the link is the following:

public int HammingWeight(uint n) {
    int sum = 0;
    while (n > 0) {
        uint t = n % 10;
        sum += t == 0 ? 0 : 1;
        n /= 10;
    }
    return sum;
}

My solution was to isolate each number and if it's one increase the sum. When I ran this on my PC it worked (yes - I know it's not the optimal solution and there are more elegant solutions considering it's binary representation).

But when I tried running in the leetcode editor it returned a wrong answer for the following input (00000000000000000000000000001011).

No real easy way to debug other then printing to the console so I printed the value of n when entering the method and got the result of 11 instead of 1011 - on my PC I got 11. If I take a different solution - one that uses bitwise right shift or calculating mod by 2 then it works even when the printed n is still 11. And I would have expected those solutions to fail as well considering that n is "wrong" (different from my PC and the site as described).

Am I missing some knowledge regarding the representation of uint? Or binary number in a uint variable?

Answer 1

Your code appears to be processing it as base 10 (decimal), but hamming weight is about base 2 (i.e. binary). So: instead if doing % 10 and /= 10, you should be looking at % 2 and /= 2.

As for what uint looks like as binary: essentially like this, but ... the CPU is allowed to lie about where each of the octets actually is (aka "endianness"). The good news is: it doesn't usually expose that lie to you unless you cheat and look under the covers by looking at raw memory. As long as you use regular operators (include bitwise operators): the lie will remain undiscovered.

---

Side note: for binary work that is about checking a bit and shuffling the data down, & 1 and >> 1 would usually be preferable to % 2 and / 2. But as canton7 notes: there are also inbuilt operations for this specific scenario which uses the CPU intrinsic instruction when possible (however: using the built-in function doesn't help you increase your understanding!).