Most efficient way to find prime factorization of 2 for a positive integer

Question

I am coding in C and wish to figure out the most efficient way to determine how many times 2 divides a number; i.e 5 = 0, 8 = 3. My question is, with this code, I utilized bitwise operations to speed up runtime, and overall the code is O(log N), is there anything computational or analytical I can do to optimize this code?

int Prime_Factor_Two(int n) {
    int k = 0;
    while(~(n&1) + 2){
        n = n >> 1;
        k +=1;
    }
    return k;
}

Answer 1

Okay, the most efficient way you say? How about (almost) a single assembly instruction?

From the GCC doc (and also available in Clang):

Built-in Function: int __builtin_ctz (unsigned int x)

Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.

unsigned Prime_Factor_Two(unsigned x) {
    return x ? __builtin_ctz(x) : 0;
}

No function calls, no loops, only one branch. If you know that the number is positive you can even remove that and just use __builtin_ctz(x).

The __builtin_ctz() built-in:

• On x86 should compile to a single assembly instruction: TZCNT (if supported) or BSF.
• On ARM should compile to two instructions: RBIT + CLZ.
• On PowerPC should compile to 31 - CNTLZ(x & -x) (assuming 32bit unsigned).
• On other platforms, maybe a handful of instructions.

To also support negative integers you can leverage the fact that the two's complement of a number preserves the least significant zeroes, and just change type from unsigned to int:

unsigned Prime_Factor_Two(int x) {
    return x ? __builtin_ctz(x) : 0;
}

Answer 2

Assuming only positive numbers and that your system uses 2's Complement notation, you can first isolate the least significant set bit using the seemingly bizarre x = x & -x operation; then, you can convert that to the set bit's position using the log2(x) function.

Here's a test program:

#include <stdio.h>
#include <math.h>

int main()
{
    int num, ans;
    do {
        printf("Enter a number: ");
        if (scanf("%d", &num) != 1 || num == 0) break;
        ans = (int)(log2(num & -num) + 0.5);
        printf("Answer is: %d\n", ans);
    } while (num > 0);
    return 0;
}

Alternatively, to avoid using floating-point stuffs and the math(s) library, you can use a bit-shift loop (this will also work for negative and zero values):

int main()
{
    int num, ans;
    do {
        printf("Enter a number: ");
        if (scanf("%d", &num) != 1) break;
        num &= -num;
        for (ans = 0; num > 1; ans++) num >>= 1;
        printf("Answer is: %d\n", ans);
    } while (num > 0);
    return 0;
}

EDIT: Of course, both of the above methods are contrived and unnecessary; a simple loop with a shifting, single-bit mask will do the trick - except for a value of zero, which is, anyway, divisible by 2 (with no remainder) infinite times:

#include <stdio.h>

int main()
{
    int num, ans, bit;
    do {
        printf("Enter a number: ");
        if (scanf("%d", &num) != 1 || num == 0) break;
        for (ans = 0, bit = 1; !(num & bit); ans++) bit <<= 1;
        printf("Answer is: %d\n", ans);
    } while (1);
    return 0;
}