Arithmetic optimization

Question

How to optimize the following (convert arithmetic to bit-wise operations)?

Optimize:

int A = B * 4
int A = B * 72
int A = B % 1
int A = B % 16
int A = (B + C) / 2
int A = (B * 3) / 8
int A = (B % 8) * 4

Saw these questions in interview.

@spug This is the exact question in an interview I had, there was no more information in the question about `A` or `B` or anything else. — A-Sharabiani, Jul 14 '17 at 13:47
Sounds like a homework that wants to remind you of bitshift operators.... — Anedar, Jul 14 '17 at 13:47
They probably want you to talk about shifts and bitwise ands, but the let the compiler figure it out is the correct answer. — Colin, Jul 14 '17 at 13:47
@FrançoisAndrieux Maybe we can convert these to some binary / bit operations to run it faster. — A-Sharabiani, Jul 14 '17 at 13:48
@AliSharabiani Well, we could. But the compiler can do it better, more reliably and with less effort. Additionally, you avoid obfuscating your code with useless and cryptic optimizations. — François Andrieux, Jul 14 '17 at 13:49
How can I do it using bit operations (shifts, bitwise and, ...) ? — A-Sharabiani, Jul 14 '17 at 13:50
For the first one as an example, int A = B * 4 can be expressed as int A = B << 2; . This is a left shift, where the operated on the right of the << operator is the exponent, the base is 2, and it becomes multiplied with the left operand, e.g. B * 2^2 — Miket25, Jul 14 '17 at 13:52
I should also comment that the third statement, int A = B%1;, will always be zero. There's no fancy bit manipulation, just modulo arithmetic realization. — Miket25, Jul 14 '17 at 14:02

Welbog · Accepted Answer · 2017-07-14T14:21:17.847

The interviewer is probably looking for your ability to convert arithmetic to bitwise operations under the misguided notion that this will be faster. The compiler will perform optimizations, so there's nothing you need to optimize. If you don't have an optimizing compiler, then the right thing to do is to profile your code to see where the performance bottlenecks are and fix them. It is unlikely that arithmetic will be your performance bottleneck.

That said, this is probably what the interviewer is looking for:

B * 4, multiplication by powers of two can be performed using bit-shift operations, such as B << 2. This achieves the same result.
B * 72, this is actually B * 8 * 9, which is B * 2^3 * (2^3 + 1) = (B*2^6) + (B*2^3). Again, the solution is to find powers of two and write them using bit-shift operations. (B << 6) + (B << 3) is the same as B * 72
B % 16, is always a number in the range 0-15 (if B is positive) this is asking for the last 4 bits of an integer, and can be found using a bit mask: B & 0xF.
etc

Note that in each case the meaning of the code is harder to follow. B * 72 is easier to read than (B << 6) + (B << 3). This process of trying to nitpick code performance without actually profiling anything is called premature optimization. If you profile your code and find its performance bottleneck really is these math operations, then you can rewrite them in optimized forms, but you have to document what the code means so that the next person who looks at it understands why the code is so messy.

I would note that, if I were the interviewer asking this question (and I wouldn't ask this question), I would prefer the answer "let the compiler do the optimizations" to just blindly finding bitwise ways of expressing the arithmetic.

How can I convert these to bitwise operations? (Gonna update the question) — A-Sharabiani, Jul 14 '17 at 13:53
We need to take into account negative numbers as well I think, because the interviewer didn't specify that the inputs would be positive. — meowgoesthedog, Jul 14 '17 at 14:05
Bit shifting two's-complement integers still works the way you expect it to for numbers that aren't near the limits of integers. You could argue that the integers aren't guaranteed to be in two's-complement format, but I would argue that you shouldn't be doing bit shifting in the first place unless you know your integer format. — Welbog, Jul 14 '17 at 14:09
Yeah, but bit-shifting signed integers is a bad idea, and the kind of code that only really belongs on high-pressure embedded platforms; anywhere else, it's premature optimisation that obfuscates the code and renders it inherently unportable. Still, I guess to ensure that 2's complement is available, we could use the `std::intN_t` types, as those are required to be 2's complement and cannot be defined otherwise. — underscore_d, Jul 14 '17 at 14:11

meowgoesthedog · Answer 2 · 2017-07-15T00:10:16.493

1

All of these calculations can be done by bit-shifts; however, this would only work on positive numbers. We need to have a special case for negative inputs, since the interviewer didn't specify which!

Multiplication by 4 = 2² can be done by left-shifting by 2 bits.

int A = (B < 0) ? -((-B) << 2)) : B << 2;

The negative number will overflow and give the wrong result if we directly do a shift on it, so we operate on minus-it.

72 = 64 + 8 = 2⁶ + 2³. Thus:

int A = (B < 0) ? -(((-B) << 6) + ((-B) << 3)) : (B << 6) + (B << 3)

The modulus for negative numbers in the C++ standard is equivalent to:

neg_number % N = -((-neg_number) % N); (Test it for yourself)

But this has no effect on modulus by 1! Thus int A = 0;

Using an AND (&) as Welbog said:

int A = (B < 0) ? -((-B) & 0xF) : B & 0xF;

Do the same as previously said, but on the sum; using a right shift by 1:

int A = (B + C < 0) ? -((-(B+C)) >> 1) : (B + C) >> 1;

int A = (B < 0) ? -(((-B) << 1 - B) >> 3) : (B << 1 + B) >> 3;

int A = (B < 0) ? -(((-B) & 7) << 2) : (B & 7) << 2;

edited Jul 15 '17 at 00:10

answered Jul 14 '17 at 14:04

meowgoesthedog

14,670
4
27
40

1

Note that for bitshift operations (`<<`, `>>`), you don't need to worry about negatives if your integers are in two's-complement format, as long as your types are signed. I.e., `B << 2` will work even if B is negative, if B is represented in two's-complement. For the mask operations (`&`, `|`), things are different. – Welbog Jul 14 '17 at 14:11
@Welbog oh damn I didn't know that, thank you. Is that why there are two sets of x86 shift instructions? (`shl` vs `sal` and for right) – meowgoesthedog Jul 14 '17 at 14:15
Seems that way: https://stackoverflow.com/questions/8373415/difference-between-shl-and-sal-in-80x86 – Welbog Jul 14 '17 at 14:17
1

@spug, you meant to say `int A = 0` for three and not `int A = B`? The remainder for any integer divided by one is zero. – Miket25 Jul 14 '17 at 23:59
@miket25 oops, yes, thank you – meowgoesthedog Jul 15 '17 at 00:10

Arithmetic optimization

2 Answers2