5 ms·
My takeaway (since I'm okay at multiplying numbers) is the algorithm for figuring out the binary digits of a number. I've always just done "okay, it's bigger th
by tgb 9y ago
My takeaway (since I'm okay at multiplying numbers) is the algorithm for figuring out the binary digits of a number. I've always just done "okay, it's bigger than 256, so subtract that and then it's bigger than 64 so subtract, etc." I much prefer this strategy of successively divide by 2 and discard remainder, mark a 1 for each time that the result is odd and 0 for even.
- romwell 9y agoThat's, essentially, the algorithm for computing the representation of a number in a given base: divide by the base and write down the remainders. To build up intuition on how this works, do it with base 10. What are the digits of the number 8675309 ? Just remainders after repeatedly dividing by 10. Now when it's almost obvious it works for base 10, you realize there's no reason it wouldn't work the same way for other bases. Hence the algorithm.
- tgb 9y agoYou're of course completely correct, but I feel like that misses the point. The great thing about this algorithm is not that it works - there are plenty of ways to figure out the binary representation of a number. Rather, it's that it only needs operations that are easy to perform and requires little state to remember. I'd much rather divide by two and round down than subtract the largest power of two that's less than my number from it. And I don't have to remember which power of N I last worked to know how many zeros I need to add before using the next power of 2 that fits in my number.