Trouble with bitwise manipulation

Question

OK, guys, I know what I want to do, but I don't know if it already exists (as a function or theoretically) or how to phrase it, so I need your help :

• Let's say we've got a binary number : (msb)10101110(lsb)
• Starting from bit X, I want to zero-out all other bits (going left), as soon as the first zero bit is encountered.
• Do that as fast as possible, with the absolute minimum number of operations and CPU cycles needed

An example :

• Number = 10101110, Starting position = 1 (bit at place 1 = 1)
• position++ - bit at place 2 = 1, keep going
• position++ - bit at place 3 = 1, keep going
• position++ - bit at place 4 = 0, oops... zero encountered... now, everything has to be zero-ed out.

So, the final result of our imaginary function CROPLEFT(X,POS), where X=10101110, and POS=1, would return 00001110.

---

Any ideas?

Answer 1

Piece of cake.

y = ~x;    // We like working with 1's, not 0's.
y &= -y;   // Mask off all but the lowest-set bit
x &= y-1;  // Make a mask for the bits below that and apply it.

and with the position parameter added:

y = ~x & -1U<<pos; // Change 1U to a larger type if needed.
y &= -y;
x &= y-1;

The key ingredient is the second line and the fact that you can replace a value y with just its lowest set bit by applying logical and against -y. Sadly there's no such luck for getting the highest-set bit, unless you have a special cpu instruction for it, so you're lucky that your problem called for lowest.

Answer 2

OK, what the heck:

return x & ((x ^ (x + (1UL << POS))) | ((1UL << POS) - 1))

---

For what it's worth, both of them compiled with gcc-4.7 -O3. R..'s on the left, mine on the right: (using unsigned long and 1UL in both of them)

        .p2align 4,,15                          .p2align 4,,15
        .globl  zapleft                         .globl  zapleft2
        .type   zapleft, @function              .type   zapleft2, @function
zapleft:                                zapleft2:           
.LFB0:                                  .LFB1:
        .cfi_startproc                          .cfi_startproc
        movl    %esi, %ecx                      movl    %esi, %ecx
        movq    %rdi, %rax                      movl    $1, %edx
        movq    $-1, %rdx                       salq    %cl, %rdx
        salq    %cl, %rdx                       leaq    (%rdx,%rdi), %rax
        notq    %rax                            subq    $1, %rdx
        andq    %rax, %rdx                      xorq    %rdi, %rax
        movq    %rdx, %rax                      orq     %rdx, %rax
        negq    %rax                            andq    %rdi, %rax
        andq    %rdx, %rax                      ret
        subq    $1, %rax                        .cfi_endproc
        andq    %rdi, %rax              .LFE1:
        ret                             .size   zapleft2, .-zapleft2
        .cfi_endproc
.LFE0:
        .size   zapleft, .-zapleft

Answer 3

CROPLEFT(int X,int POS) {

    int mask = 1 << POS;

    while (X & mask)
        mask <<= 1;

    return (X & (mask - 1));
}