C - Get position of leftmost set bit from an 8 bit integer without loops

Question

I'm trying to make a program which prints out the position of the leftmost 1 bit in C, but without loops.

This is what I've gathered so far:

#include<stdio.h>
int main() {
    unsigned int x, y;
    printf("Enter an integer: ");
    scanf("%d", &x);
    // Bit 
    x |= x >> 4;
    x |= x >> 2;
    x |= x >> 1;
    x ^= x >> 1;
    printf("\n%d", x);
    return 0;
}

This prints out the leftmost bit as an integer, but I'm having trouble converting it to the position of its highest set bit.

128 should be 8 (1000 0000) 64 should be 7 (0100 0000)

Why not `__builtin_clz` (on GCC) or `BitScanReverse` (on MSVS)? — Giovanni Cerretani, Oct 26 '18 at 13:50
@Blaze it works, thanks, but how would I do this without using anything from math.h? The task is very limited, i am confined to only using bitwise operations, nothing else. — , Oct 26 '18 at 13:56
Are you sure about the restrictions? If you can use conditionals, you can just write `if (x & (1 << 7)) printf("7\n"); else if ...`, which seems too simple. — molbdnilo, Oct 26 '18 at 14:01
regarding: `scanf("%d", &x);` the variable 'x' is unsigned, but the format specifier '%d' is expecting the address of a signed variable. Suggest: `scanf("%u", &x);` — user3629249, Oct 26 '18 at 15:06

Giovanni Cerretani · Accepted Answer · 2018-10-26T15:21:55.500

Inspired from this question, this solution that define a loopless popcnt() should solve your problem:

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

static inline uint32_t popcnt(uint32_t x) {
    x -= ((x >> 1) & 0x55555555);
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
    x = (((x >> 4) + x) & 0x0f0f0f0f);
    x += (x >> 8);
    x += (x >> 16);
    return x & 0x0000003f;
}

static inline uint32_t firstset(uint32_t x) {
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return popcnt(x);
}

int main() {
    uint32_t x;

    printf("Enter an integer: ");
    scanf("%"SCNu32, &x);

    printf("%"PRIu32"\n", firstset(x));

    return 0;
}

C - Get position of leftmost set bit from an 8 bit integer without loops

1 Answers1