1

/* $Id$ */

     2

     4

     5

#include "../stdafx.h"

     6

#include "bitmath_func.hpp"

     7

     8

const uint8 _ffb_64[64] = {

     9

 0,  0,  1,  0,  2,  0,  1,  0,

    10

 3,  0,  1,  0,  2,  0,  1,  0,

    11

 4,  0,  1,  0,  2,  0,  1,  0,

    12

 3,  0,  1,  0,  2,  0,  1,  0,

    13

 5,  0,  1,  0,  2,  0,  1,  0,

    14

 3,  0,  1,  0,  2,  0,  1,  0,

    15

 4,  0,  1,  0,  2,  0,  1,  0,

    16

 3,  0,  1,  0,  2,  0,  1,  0,

    17

};

    18

    19

/**

    20

 * Search the first set bit in a 32 bit variable.

    21

 *

    22

 * This algorithm is a static implementation of a log

    23

 * conguence search algorithm. It checks the first half

    24

 * if there is a bit set search there further. And this

    25

 * way further. If no bit is set return 0.

    26

 *

    27

 * @param x The value to search

    28

 * @return The position of the first bit set

    29

 */

    30

uint8 FindFirstBit(uint32 x)

    31

{

    32

	if (x == 0) return 0;

    33

	/* The macro FIND_FIRST_BIT is better to use when your x is

    34

	  not more than 128. */

    35

    36

	uint8 pos = 0;

    37

    38

	if ((x & 0x0000ffff) == 0) { x >>= 16; pos += 16; }

    39

	if ((x & 0x000000ff) == 0) { x >>= 8;  pos += 8;  }

    40

	if ((x & 0x0000000f) == 0) { x >>= 4;  pos += 4;  }

    41

	if ((x & 0x00000003) == 0) { x >>= 2;  pos += 2;  }

    42

	if ((x & 0x00000001) == 0) { pos += 1; }

    43

    44

	return pos;

    45

}

    46

    47

/**

    48

 * Search the last set bit in a 64 bit variable.

    49

 *

    50

 * This algorithm is a static implementation of a log

    51

 * conguence search algorithm. It checks the second half

    52

 * if there is a bit set search there further. And this

    53

 * way further. If no bit is set return 0.

    54

 *

    55

 * @param x The value to search

    56

 * @return The position of the last bit set

    57

 */

    58

uint8 FindLastBit(uint64 x)

    59

{

    60

	if (x == 0) return 0;

    61

    62

	uint8 pos = 0;

    63

    64

	if ((x & 0xffffffff00000000ULL) != 0) { x >>= 32; pos += 32; }

    65

	if ((x & 0x00000000ffff0000ULL) != 0) { x >>= 16; pos += 16; }

    66

	if ((x & 0x000000000000ff00ULL) != 0) { x >>= 8;  pos += 8;  }

    67

	if ((x & 0x00000000000000f0ULL) != 0) { x >>= 4;  pos += 4;  }

    68

	if ((x & 0x000000000000000cULL) != 0) { x >>= 2;  pos += 2;  }

    69

	if ((x & 0x0000000000000002ULL) != 0) { pos += 1; }

    70

    71

	return pos;

    72

}