1
string convertDigitsToBinary(int n) {
        string ans;
        if (n == 0) return "0";

        while (n > 0) {
        int rem = n % 2; 
        ans.push_back((char)('0' + rem));
        n /= 2;
        }

        reverse(ans.begin(), ans.end());
        return ans;
}

I understand how the algorithm works to % the number by 2 and then use the remainder to create the binary representation, I just don't know how it works.

I guess I don't see the connection in using the remainder to determine whether the bits are 0 or 1

So in the code above: N = 6 would be 110

3

Remainder is the overkill way of testing the lowest bit. If you think about it any value % 2 will produce only either 0 or 1, which happens corresponds to the value of the lowest bit.

A more mathematical or alternate way of thinking of is even or odd, which can also obtained by % with 2. If the value is even, % by 2 yields zero. And if the value is even, then that means that the lowest bit is zero, so % by 2 yielding zero means the lowest bit is zero.

The lowest bit in binary integers represents 20. The other positions in increasing order represent 21, and beyond. The only way to make an odd number in binary is to add in 20 = 1, which is done by setting the lowest bit. (Note this also applies to negative numbers as long as they are stored in 2's complement form as all modern computers do).

Re: the overkill, in most languages you can do a simpler mask with constant 1, such as n & 1, which is a more direct way of checking the value of the lowest bit. Divide by 2 is the mathematical way of shifting the bits one position to the right; as with masking, most languages have a the more direct way of shifting, e.g. n >>= 1; These are often preferred because they have fewer issues, such as the quirks of dealing with mod and division of negative integers (computer division, especially with integers, differs subtly from mathematical division, which would result in fractions or reals). Also, especially on older processors the simpler way was faster, being doable with simple logic instead of a divider which is fairly complex.

| improve this answer | |
  • 1
    Any (non-dumb) compiler will map a % (n^2) to an equivalent bitwise and (like it will map a / 2 to a right shift). It's one of the most trivial optimizations you can build in a compiler. So it's not overkill at all. – qwerty_so Nov 21 '16 at 6:30
  • @ThomasKilian, yes, but only when the compiler can determine that the input is positive. – Erik Eidt Nov 21 '16 at 16:34
  • Well, 2 seems to be quite in the range of positive numbers. – qwerty_so Nov 21 '16 at 17:02
  • @ThomasKilian, very funny, ar ar ;) @ others, it is n that needs to be non-negative, which in this case it isn't necessarily known as it is declared int. and yes, the compiler can do some conditional code sequences that avoid the full divide; still this is what makes n & 1 and n >> 1 "simpler". – Erik Eidt Nov 21 '16 at 17:56
  • I once wrote a Modula2 compiler with code generation for an IBM/370, so I quite know what can be done in code optimization. Since the above example uses a % 2, the constant value is well recognized as n^2 and converted to a logical and. So actually there is no difference in writing it explicitly. Except the compiler (coder) is 'dumb'. – qwerty_so Nov 21 '16 at 18:04
1

The general algorithm for formatting a positive integer as a string in any base is:

  1. start with an empty string s and a working integer n
  2. append the bottom (least significant) digit of n in your desired base to s
  3. divide n by the base (truncate to integer)
  4. repeat from 2 until n is zero

I guess I don't see the connection in using the remainder to determine whether the bits are 0 or 1

But the least significant digit of n in base b is defined to be n % b. Try it in base 10 if it helps to confirm your intuition, but base 2 is no different.

As for

Remainder is the overkill way of testing the lowest bit

remainder (modulo) is the canonical way of doing this. Using bitwise & instead is an optimization for bases which are powers of two.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.