-1

Assume the following operation:

1 << bit

where bit may take values from 0 and up. Knowing the result of left-shift operation, how can I derive the bit value?

I know that left bit-shifting is equivalent to multiplication of the original number (1 in my example) by a power of 2, e.g. :

1 << 0 => 1 * 2^0 = 1

1 << 1 => 1 * 2^1 = 2

and so on.

So how can I get the power value?

stark
  • 12,615
  • 3
  • 33
  • 50
Mark
  • 6,052
  • 8
  • 61
  • 129
  • Do a right-shift bit by bit until the value is `1`? – Some programmer dude Jun 17 '20 at 16:05
  • bit is log base 2. – stark Jun 17 '20 at 16:07
  • 1
    Left-shifting by `n` bits causes the value to lose `n` bits from the left, thus I think it cannot be reversed – Ayman Al-Qadhi Jun 17 '20 at 16:07
  • Please [edit] your question to clarify: Will it *always* be `1` that is shifted? That the operation is always `1 << n`, with `1` on the left-hand-side? The answer to your question depends very much on this. Also, can `n` ever be larger than the possible bit-width of `int`? – Some programmer dude Jun 17 '20 at 16:13
  • 1
    There are fast algorithms for log2, e.g. [here](https://stackoverflow.com/a/11376759/509868). – anatolyg Jun 17 '20 at 16:20
  • 1
    Does this answer your question? [Fast computing of log2 for 64-bit integers](https://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers) – Alex Lop. Jun 17 '20 at 19:15

4 Answers4

1

Reverse the operation.

Take the resulting value and shift right by one, counting each time you do, until you get 1.

unsigned int val = 1 << bit;
int count = 0;
while (val > 1) {
    val >>= 1;
    count++;
}
dbush
  • 205,898
  • 23
  • 218
  • 273
  • Of course, that's only if no high bits were shifted off the end. – Charles Duffy Jun 17 '20 at 16:09
  • @CharlesDuffy The OP states that it's always `1 << n`, i.e. no high bits. – Some programmer dude Jun 17 '20 at 16:11
  • 1
    In the body, yes, but the title states a more general question. It's hard to tell if the example in the body is what they mean to ask, or just an accident of insufficient imagination in developing said example. (It's not exactly uncommon here for folks to show trivial examples and yet intend to get a more robust answer they can put to other uses!) – Charles Duffy Jun 17 '20 at 16:12
  • 1
    Note that `1` is of type `int` thus `1 << bit` is not safe as it may result in integer overflow. Better to use `1u << bit`. – Alex Lop. Jun 17 '20 at 19:13
0

Shifting n bits to either side causes the shifted value to lose n bits from that side, so the operation is irreversible.

For example, if we have the binary value 10101010, and we left-shifted it by 4, then the value will become 10100000. Performing a right shift by 4 wont bring the lost bits back.

Ayman Al-Qadhi
  • 129
  • 4
  • The OP states that it's always `1 << n`, i.e. no high bits. – Some programmer dude Jun 17 '20 at 16:12
  • @Someprogrammerdude, they only show an example of `1 << n`, but do they ever say that that's the _only_ case they care about? Indeed, they explicitly say "1 *in my example*", indicating that the example is... well... only an example, as opposed to the complete/exhaustive case. – Charles Duffy Jun 17 '20 at 16:13
  • Even if not always 1, you can do repeated *left* shift, and discover the shift count, even if there was overflow (but I cannot imagine where such a thing would be useful). – anatolyg Jun 17 '20 at 16:14
  • 1
    OP is *not asking* if the original value can be recovered, but if the number of shifts can be deduced. Provided there is at least one `1` bit remaining, and the original value is known, the answer is "yes". – Weather Vane Jun 17 '20 at 16:18
  • @WeatherVane That's the point. If the old value is no longer available, then number of shifted bits cannot be deduced (or at least deduced reliably) – Ayman Al-Qadhi Jun 17 '20 at 16:23
0

You can use ffs to find the first least significant bit set:

#include <stdlib.h>
int main() {
    int bit = 4;
    int val = 1 << bit;
    // ffs counts from 1, so decrement it 
    int bit2 = ffs(val) - 1;
    printf("%d %d\n",  bit, bit2); // prints: "4 4"
}
KamilCuk
  • 120,984
  • 8
  • 59
  • 111
  • 1
    It should be noted that [`ffs`](https://pubs.opengroup.org/onlinepubs/9699919799/functions/ffs.html) is a POSIX function, and thus its use isn't portable to non-POSIX systems (like e.g. Windows). – Some programmer dude Jun 17 '20 at 16:20
0

If you search a non pure C solution. You can use compiler intrinsics to count the number of trailing zeros of a word. Depending on your processor, it will be implemented with a fast instruction.

If __builtin_ctzll is not defined (i.e. it returns always 0), you can use 64 - __builtin_clzll.

Checking before that only one bit is set. Something like

#include <stdio.h>
#include <inttypes.h>

unsigned int pof2(uint64_t n) __attribute__((const));

unsigned int pof2(uint64_t n)
{
   if(__builtin_popcountll(n) == 1)
    return __builtin_ctzll(n);
  return 0;
}

int main(void)
{
  int i;
  for(i=0; i<65; i++)
    printf("i=%d 1<<%d=%lu po2=%u\n", i, i, 1ull<<i, pof2(1ull<<i));
  return 0;
}

Result:

i=0 1<<0=1 po2=0
i=1 1<<1=2 po2=1
i=2 1<<2=4 po2=2
i=3 1<<3=8 po2=3
i=4 1<<4=16 po2=4
i=5 1<<5=32 po2=5
i=6 1<<6=64 po2=6
i=7 1<<7=128 po2=7
i=8 1<<8=256 po2=8
i=9 1<<9=512 po2=9
i=10 1<<10=1024 po2=10
i=11 1<<11=2048 po2=11
i=12 1<<12=4096 po2=12
i=13 1<<13=8192 po2=13
i=14 1<<14=16384 po2=14
i=15 1<<15=32768 po2=15
i=16 1<<16=65536 po2=16
i=17 1<<17=131072 po2=17
i=18 1<<18=262144 po2=18
i=19 1<<19=524288 po2=19
i=20 1<<20=1048576 po2=20
i=21 1<<21=2097152 po2=21
i=22 1<<22=4194304 po2=22
i=23 1<<23=8388608 po2=23
i=24 1<<24=16777216 po2=24
i=25 1<<25=33554432 po2=25
i=26 1<<26=67108864 po2=26
i=27 1<<27=134217728 po2=27
i=28 1<<28=268435456 po2=28
i=29 1<<29=536870912 po2=29
i=30 1<<30=1073741824 po2=30
i=31 1<<31=2147483648 po2=31
i=32 1<<32=4294967296 po2=32
i=33 1<<33=8589934592 po2=33
i=34 1<<34=17179869184 po2=34
i=35 1<<35=34359738368 po2=35
i=36 1<<36=68719476736 po2=36
i=37 1<<37=137438953472 po2=37
i=38 1<<38=274877906944 po2=38
i=39 1<<39=549755813888 po2=39
i=40 1<<40=1099511627776 po2=40
i=41 1<<41=2199023255552 po2=41
i=42 1<<42=4398046511104 po2=42
i=43 1<<43=8796093022208 po2=43
i=44 1<<44=17592186044416 po2=44
i=45 1<<45=35184372088832 po2=45
i=46 1<<46=70368744177664 po2=46
i=47 1<<47=140737488355328 po2=47
i=48 1<<48=281474976710656 po2=48
i=49 1<<49=562949953421312 po2=49
i=50 1<<50=1125899906842624 po2=50
i=51 1<<51=2251799813685248 po2=51
i=52 1<<52=4503599627370496 po2=52
i=53 1<<53=9007199254740992 po2=53
i=54 1<<54=18014398509481984 po2=54
i=55 1<<55=36028797018963968 po2=55
i=56 1<<56=72057594037927936 po2=56
i=57 1<<57=144115188075855872 po2=57
i=58 1<<58=288230376151711744 po2=58
i=59 1<<59=576460752303423488 po2=59
i=60 1<<60=1152921504606846976 po2=60
i=61 1<<61=2305843009213693952 po2=61
i=62 1<<62=4611686018427387904 po2=62
i=63 1<<63=9223372036854775808 po2=63
i=64 1<<64=1 po2=0
Patrick Schlüter
  • 11,394
  • 1
  • 43
  • 48