0

My current (bad) solution:

void initialization(void) {
    for (unsigned int i = 0; i < pageSize; i++) {
        if (2 << i == pageSize) {
            offset = i;
            break;
        }
    }
}

Example: pageSize = 4096, Solve for x in, pageSize = 2^x

I feel like there should be a much better way if doing this without a loop and without math.h. Especially since the base is always 2 and there's a lot of stuff with bit shifting involving powers of 2.

Will
  • 604
  • 1
  • 5
  • 18
  • `__builtin_ctz(pageSize) - 1`, maybe. – Ry- Oct 22 '18 at 21:00
  • By the way `2 << i` is 2 to the power of i+1, not just to the power of i. 2 already has a shift built into it in some sense. – harold Oct 22 '18 at 21:07
  • What about https://stackoverflow.com/questions/41369765/standard-way-to-call-ffsl-in-c – Jerry Jeremiah Oct 22 '18 at 21:07
  • If My guess about ffsl is right then this might be useful: https://en.wikipedia.org/wiki/Find_first_set#Tool_and_library_support – Jerry Jeremiah Oct 22 '18 at 21:09
  • 1
    That's an infinite loop if pagesize turns out not to be a power of 2. – rici Oct 22 '18 at 21:09
  • `for (int i=0;;) if (pageSize >> i == 1) return i;` although there are faster versions. – jxh Oct 22 '18 at 21:13
  • @JerryJeremiah I found the solution on http://graphics.stanford.edu/~seander/bithacks.html from that question. My problem was I didn't really know what I was asking for. I want to find the highest bit set and that page has multiple solutions. – Will Oct 22 '18 at 21:20

2 Answers2

0

My problem was I didn't really know what I was looking for. I needed to find the highest bit set (or most significant bit set, MSB). Multiple solutions can be found on Bit Twiddling Hacks. Hopefully my poorly worded question helps others Googling similarly poorly worded questions at some point.

For my specific purpose this solution works:

int v = pageSize; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp

t.u[__ORDER_LITTLE_ENDIAN__==LITTLE_ENDIAN] = 0x43300000;
t.u[__ORDER_LITTLE_ENDIAN__!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__ORDER_LITTLE_ENDIAN__==LITTLE_ENDIAN] >> 20) - 0x3FF;
Will
  • 604
  • 1
  • 5
  • 18
0

clang is capable of recognizing what this function does:

unsigned int log2i(unsigned int n) {
    unsigned int i = 0;

    while (n >>= 1) {
        i++;
    }

    return i;
}

log2i:
        shr     edi
        lzcnt   ecx, edi
        mov     eax, 32
        sub     eax, ecx
        ret

But since you have an exact power of two, in practice, it’s probably fine and better to use a GCC/clang/others builtin even if it’s not standard C:

unsigned int log2Exact(unsigned int n) {
    return __builtin_ctz(n);
}

log2Exact:
        tzcnt   eax, edi
        ret
Ry-
  • 218,210
  • 55
  • 464
  • 476