-1

Dear all C programmer:

X = 1 << N; (left shift)

how to recover N from X ?

Thanks

Franck 38
  • 5
  • 2

3 Answers3

2

N in this case is the bit position where you shifted in a 1 at. Assuming that X here only got one bit set. Then to find out what number that bit position corresponds to, you have to iterate through the data and mask with bitwise AND:

for(size_t i=0; i<sizeof(X)*8; i++)
  if(X & (1<<i))
    printf("%d", i);

If performance is important, then you'd make a look-up table with all possible results instead.

Lundin
  • 195,001
  • 40
  • 254
  • 396
  • If `sizeof X>sizeof(int) && sizeof X >sizeof(size_t)` you get UB even when you add a -1. In this case you would need a cast to the type of X first. – 12431234123412341234123 Jan 13 '21 at 11:03
  • `8` assumes that `CHAR_BIT==8`, which can be false. Why not use `CHAR_BIT` directly? And `1<<(sizeof(int)*CHAR_BIT)` can be UB when `sizeof(int)=>sizeof(size_t)`, i think you forgot a `-1`. – 12431234123412341234123 Jan 13 '21 at 11:04
  • 1
    @12431234123412341234123 Because I'm not interested in providing portability to extremely exotic, fictional or otherwise dysfunctional systems. The only real-world computers I know that actually have other char sizes are various obsolete TI DSPs and if someone decides to program those in C while at the same time aimlessly importing random standard C libs found on the internet, then that incompetence is their problem, not mine. – Lundin Jan 13 '21 at 11:51
0

In a while loop, keep shifting right until X==1, record how many times you have to shift right and the counter will give you N.

int var = X;
int count = 0;
while (var != 1){
    var >>= 1; 
    count++;
}
printf("N is %d", count);
Gerhardh
  • 11,688
  • 4
  • 17
  • 39
charmanderx86
  • 28
  • 5
  • This is problematic when X `var` is negative or when `X` has the type `unsigned` and the highest bit is set. Better use `unsigned` for var. Even better would be `uintmax_t` since it could be that `sizeof X>=sizeof(int)`. – 12431234123412341234123 Jan 13 '21 at 11:01
  • @12431234123412341234123: If `X` is negative, then the shift in `X = 1 << N;` overflowed, and none of the answers work because the behavior of the program is not defined by the C standard. – Eric Postpischil Jan 13 '21 at 11:59
0

Try this (flsl from here which is available from string.h on macOS) :

int flsl(long mask)
{
    int bit;

    if (mask == 0) return (0);
    for (bit = 1; mask != 1; bit++)
        mask = (unsigned long)mask >> 1;
    return (bit);
}

unsigned char binlog(long mask) { return mask ? flsl(mask) - 1 : 0; }

int x = 1 << 20;
printf("%d\n", binlog(x)); ===> 20
dspr
  • 2,383
  • 2
  • 15
  • 19