author | skidd13 |
Mon, 26 Nov 2007 17:50:22 +0000 | |
changeset 7971 | 8509d595142a |
child 8000 | 2ba28bc428f1 |
permissions | -rw-r--r-- |
7971
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
1 |
/* $Id$ */ |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
2 |
|
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
3 |
/** @file bitmath_func.cpp */ |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
4 |
|
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
5 |
#include "../stdafx.h" |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
6 |
#include "bitmath_func.hpp" |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
7 |
|
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
8 |
const uint8 _ffb_64[64] = { |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
17 |
}; |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
18 |
|
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
19 |
/** |
8509d595142a
(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. |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
21 |
* |
8509d595142a
(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 |
8509d595142a
(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 |
8509d595142a
(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 |
8509d595142a
(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. |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
26 |
* |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
27 |
* @param x The value to search |
8509d595142a
(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 |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
29 |
*/ |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
30 |
uint8 FindFirstBit(uint32 x) |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
31 |
{ |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
32 |
if (x == 0) return 0; |
8509d595142a
(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 |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
34 |
not more than 128. */ |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
35 |
|
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
36 |
uint8 pos = 0; |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
37 |
|
8509d595142a
(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; } |
8509d595142a
(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; } |
8509d595142a
(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; } |
8509d595142a
(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; } |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
42 |
if ((x & 0x00000001) == 0) { pos += 1; } |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
43 |
|
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
44 |
return pos; |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
45 |
} |