author | skidd13 |
Mon, 26 Nov 2007 17:50:22 +0000 | |
changeset 8467 | 2f293250afac |
child 8496 | 8a4bdf20acb7 |
permissions | -rw-r--r-- |
8467
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
1 |
/* $Id$ */ |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
2 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
3 |
/** @file bitmath_func.cpp */ |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
4 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
5 |
#include "../stdafx.h" |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
6 |
#include "bitmath_func.hpp" |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
7 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
8 |
const uint8 _ffb_64[64] = { |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
9 |
0, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
10 |
3, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
11 |
4, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
12 |
3, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
13 |
5, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
14 |
3, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
15 |
4, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
16 |
3, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
17 |
}; |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
18 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
19 |
/** |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
20 |
* Search the first set bit in a 32 bit variable. |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
21 |
* |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
22 |
* This algorithm is a static implementation of a log |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
23 |
* conguence search algorithm. It checks the first half |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
24 |
* if there is a bit set search there further. And this |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
25 |
* way further. If no bit is set return 0. |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
26 |
* |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
27 |
* @param x The value to search |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
28 |
* @param The position of the first bit set |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
29 |
*/ |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
30 |
uint8 FindFirstBit(uint32 x) |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
31 |
{ |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
32 |
if (x == 0) return 0; |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
33 |
/* The macro FIND_FIRST_BIT is better to use when your x is |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
34 |
not more than 128. */ |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
35 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
36 |
uint8 pos = 0; |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
37 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
38 |
if ((x & 0x0000ffff) == 0) { x >>= 16; pos += 16; } |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
39 |
if ((x & 0x000000ff) == 0) { x >>= 8; pos += 8; } |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
40 |
if ((x & 0x0000000f) == 0) { x >>= 4; pos += 4; } |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
41 |
if ((x & 0x00000003) == 0) { x >>= 2; pos += 2; } |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
42 |
if ((x & 0x00000001) == 0) { pos += 1; } |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
43 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
44 |
return pos; |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
45 |
} |