Fanciful Math

In a prior, previous post, I pondered what the largest possible number could be had from a carry-less multiplication of two 8-bit numbers. In a multiplication featuring carries, the obvious answer is 0xff * 0xff = 0xffff. However, without carries, any “column” with more than one “1” bit is ignored.

One approach to this would be to brute force 1 … 255 * 1 … 255 (inclusive) without carries. I didn’t do that.

My solution, in contrast, was to consider the largest number that I could slide over by 7 bits without affecting the number in an XOR operation. Obviously, I’d want to maximize the amount of most-significant bits. I came up with 0b11111110 << 7 + 0b11111110. Written another way, this is 0b11111110 * 0b10000001. The answer ends up being 0b0111111111111110 or 32,766.

Is it the largest number possible in such a multiplication? Who knows. I’m not going to check it. What’s important is the relationship between multiplication of two binary number in such a fashion and both a bitwise shift and addition.