/* 
 * ffoz-t.c : Routines to find the position of first 1/0 bit from left/right
 *            in a number, and a main function to test the code.
 *
 * Copyright (C) 2006, Sandeep Kumar <shimple0@yahoo.com>
 *                     Homepage : http://sandeepkumar.fortunecity.com/
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
 * more details.
 */

#include <stdint.h>


/*
 * IMPORTANT :
 *
 *     You can safely change parameter types (NType) to any of (8, 16, 32, 64
 *     and so on, unsigned int types) w/o requiring any change in function
 *     bodies when LOOP_UNROLL is _not_ defined.
 *
 *     For LOOP_UNROLL case, you also need to define NUMBER_SIZE in accordance
 *     with desired type. You will also need to add some code in case you need
 *     to go beyond uint64_t.
 */

/*
 * NType indicates the type of numbers, in which you want to find the occurence
 * of first zero or one from left/right.
 */
typedef  uint32_t  NType;

/* Define number size as number of bits in NType */
#define  NUMBER_SIZE  32

/* Define LOOP_UNROLL to work with loop-unrolled versions */
/* #define  LOOP_UNROLL  1 */

#if  defined(LOOP_UNROLL) && !defined(NUMBER_SIZE)
#error "You need to define NUMBER_SIZE appropriately, to work with LOOP_UNROLL"
#endif


inline int ffzr (NType number) __attribute__((always_inline));
inline int ffzl (NType number) __attribute__((always_inline));


/*
 * Find First One from LSBit (Right) end.
 *
 * Returns the bit no. of first bit set to '1' from LSBit end.
 * Bit numbering (MSBit -> LSBit) : 63 ... 0
 *
 * In case all bits are zero, it returns "-1" (You can choose any invalid
 * bit number to indicate this condition).
 *
 */

int ffor (NType number)
{
    register __typeof__(number) temp;
    int pos = 0;

#if !defined(LOOP_UNROLL)
    int shiftcount = ((sizeof(number) * 8) / 2);
#endif

    /* First check if number is non-zero i.e. does it have any '1' bit? */

    if (0 == number) {
        return (-1);
    }

    /* Isolate the first '1' bit from right. */

    number = (number ^ (number & (number - 1)));

#if !defined(LOOP_UNROLL)

    /*
     * Now exactly one bit is set to '1' in number. So "equality to 1" can
     * be used as the termination condition for while loop.
     */

    while (1 != number) {
        if (0 != (temp = (number >> shiftcount))) {
            number = temp;
            pos += shiftcount;
        }

        shiftcount >>= 1;
    }

#else   /* LOOP_UNROLL is defined. */

#if (NUMBER_SIZE >= 64)
    temp = (number >> 32);
    if (0 != temp) {
        number = temp;
        pos += 32;
    }
#endif

#if (NUMBER_SIZE >= 32)
    temp = (number >> 16);
    if (0 != temp) {
        number = temp;
        pos += 16;
    }
#endif

#if (NUMBER_SIZE >= 16)
    temp = (number >> 8);
    if (0 != temp) {
        number = temp;
        pos += 8;
    }
#endif

    /* Minimum number size is 8-bit numbers */

    temp = (number >> 4);
    if (0 != temp) {
        number = temp;
        pos += 4;
    }

    temp = (number >> 2);
    if (0 != temp) {
        number = temp;
        pos += 2;
    }

    if (0 != (number >> 1)) {
        pos += 1;
    }

#endif  /* LOOP_UNROLL */

    return pos;
}


/*
 * Find First Zero from LSBit (Right) end.
 *
 * Returns the bit no. of first bit set to '0' from LSBit end.
 * Bit numbering (MSBit -> LSBit) : 63 ... 0
 *
 * In case all bits are one, it returns "-1" (You can choose any invalid
 * bit number to indicate this condition).
 *
 */

int ffzr (NType number)
{
    return ffor(~number);
}

/*
 * You can also make following amendments to ffor to get the
 * functionality of ffzr.
 */

/**
    // First check if number has any '0' bit?

    if ((~0) == number) {
        return (-1);
    }

    // Isolate the first '0' bit from right.

    number = ((number + 1) ^ (number & (number + 1)));
**/


/*
 * Find First One from MSBit (Left) end.
 *
 * Returns the bit no. of first bit set to '1' from MSBit end.
 * Bit numbering (MSBit -> LSBit) : 63 ... 0
 *
 * In case all bits are zero, it returns "-1" (You can choose any invalid
 * bit number to indicate this condition).
 *
 */

int ffol (NType number)
{
    int pos = ((sizeof(number) * 8) - 1);

    register __typeof__(number) mask = (~0);
    register __typeof__(number) temp;
    
#if !defined(LOOP_UNROLL)
    int shiftcount = (sizeof(number) * 8);
#endif

    /* First check if number is non-zero i.e. does it have any '1' bit? */

    if (0 == number) {
        return (-1);
    }

#if !defined(LOOP_UNROLL)

    /*
     * (((__typeof__(number))(~0) >> 1) + 1) generates the values 0x80,
     * 0x8000, 0x80000000 and so on for argument types of uint8_t, uint16_t,
     * uint32_t and so on respectively.
     */

    while ( (((__typeof__(number))(~0) >> 1) + 1) != number) {
        shiftcount >>= 1;
        mask <<= shiftcount;

        if (0 == (temp = (mask & number))) {
            number <<= shiftcount;
            pos -= shiftcount;
        } else {
            number = temp;
        }
    }

#else   /* LOOP_UNROLL is defined. */

#if (NUMBER_SIZE >= 64)
    mask <<= 32;

    if (0 == (temp = (mask & number))) {
        number <<= 32;
        pos -= 32;
    } else {
        number = temp;
    }
#endif

#if (NUMBER_SIZE >= 32)
    mask <<= 16;

    if (0 == (temp = (mask & number))) {
        number <<= 16;
        pos -= 16;
    } else {
        number = temp;
    }
#endif

#if (NUMBER_SIZE >= 16)
    mask <<= 8;

    if (0 == (temp = (mask & number))) {
        number <<= 8;
        pos -= 8;
    } else {
        number = temp;
    }
#endif

    /* Minimum number size is 8-bit numbers */

    mask <<= 4;

    if (0 == (temp = (mask & number))) {
        number <<= 4;
        pos -= 4;
    } else {
        number = temp;
    }

    mask <<= 2;

    if (0 == (temp = (mask & number))) {
        number <<= 2;
        pos -= 2;
    } else {
        number = temp;
    }

    mask <<= 1;

    if (0 == (mask & number)) {
        pos -= 1;
    }

#endif  /* LOOP_UNROLL */

    return pos;
}


/*
 * Find First Zero from MSBit (Left) end.
 *
 * Returns the bit no. of first bit set to '0' from MSBit end.
 * Bit numbering (MSBit -> LSBit) : 63 ... 0
 *
 * In case all bits are one, it returns "-1" (You can choose any invalid
 * bit number to indicate this condition).
 *
 */

int ffzl (NType number)
{
    return ffol(~number);
}


int main ()
{
    int number=0;

    scanf("%d",&number);

    printf("number = %lx, ffor = %d, ffzr = %d, ffol = %d, ffzl = %d\n", number,
        ffor(number), ffzr(number), ffol(number), ffzl(number));

    return 0;
}