Left shift loop formula

Question

I found the following code in a program example:

const unsigned int n = /* something */
unsigned int i = 1;
for (unsigned int j = 1; j < n-1; ++j) {
    i <<= 1;
}

Is there a direct formula to compute i from n without a loop ?

Don't bother, really, any half-decent compiler will optimize the loop away. — Hans Passant, Nov 17 '13 at 13:51
@HansPassant I don't think I agree. Why obfuscate the code with a loop like this? — jrok, Nov 17 '13 at 13:52
@jrok - Why tinker with working code that doesn't need to be optimized? Do you really think that abhishek's snippet is not an obfuscation? Are you sure it is accurate? — Hans Passant, Nov 17 '13 at 14:12
@HansPassant I wrote the comment before Abhishek edited his answer :) — jrok, Nov 17 '13 at 14:22

score 3 · Answer 1 · 2013-11-17T14:13:29.870

3

You can use:

i = 1 << (n - 2);

or more strict:

#include <limits.h> /* for CHAR_BIT */

const unsigned int n = /* something */;
unsigned int i  = 1;

if( (n - 2) > 0 && (n - 2) < (sizeof(i) * CHAR_BIT) ) {
  i = 1 << (n - 2);
}

edited Nov 17 '13 at 14:13

answered Nov 17 '13 at 13:49

Abhishek Bansal · Accepted Answer · 2013-11-17T14:24:11.663

3

More accurately:

assuming unsigned int is 16 bits (minimum as specified by C++ standard)

i = ( n < 18 ) ? ( ( n >= 2 ) ? ( 1 << (n-2) ) : 1 ) : 0;

edited Nov 17 '13 at 14:24

answered Nov 17 '13 at 13:53

Abhishek Bansal

12,589
4
31
46

1

+1 Exactly -- Shift by negative value is undefined at best. http://stackoverflow.com/questions/4945703/left-shifting-with-a-negative-shift-count – Aki Suihkonen Nov 17 '13 at 13:54
2

@AkiSuihkonen: well, still incomplete though; if an `unsigned int` as 32 bits, then `1 << 40` will be undefined too; so you need to guard both against underflow and overflow. – Matthieu M. Nov 17 '13 at 13:56
1

But if `unsigned int` isn't 32 bits, then your magic number will be wrong. – Mike Seymour Nov 17 '13 at 14:07
@MikeSeymour Well I hope now it takes into account the minimum range specification as per C++ standard. However, the original code posted by OP didn't have this check either. – Abhishek Bansal Nov 17 '13 at 14:15
@AbhishekBansal: Indeed; it would be better to omit that check (documenting the precondition on `n`), or use a value calculated from `sizeof i`. Now, your magic number is wrong if `unsigned int` isn't 16 bytes. – Mike Seymour Nov 17 '13 at 14:17
@MikeSeymour: I would not say it's wrong; it is restricted, but technically correct, and without any more specification for a valid input range for `n` there is little what can do. – Matthieu M. Nov 17 '13 at 14:18
@MatthieuM.: Sorry, "wrong" was a simplification of "not a valid optimisation unless there are restrictions on the inputs that we don't know about". I usually try not to be too pedantic at the weekend; perhaps I should steer clear of SO today. – Mike Seymour Nov 17 '13 at 14:25

Left shift loop formula

2 Answers2