1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
/* This file is part of the Spring engine (GPL v2 or later), see LICENSE.html */
/**
* @brief Bit twiddling operations
*
* Bit twiddling shortcuts for various
* operations; see http://graphics.stanford.edu/%7Eseander/bithacks.html
* for details.
*/
#ifndef _BITOPS_H
#define _BITOPS_H
#ifdef _MSC_VER
#include <intrin.h>
#endif
/**
* @brief Next power of 2
* @param x The number to be rounded
* @return the rounded number
*
* Rounds an unsigned integer up to the
* next power of 2; i.e. 2, 4, 8, 16, etc.
*/
static inline unsigned int next_power_of_2(unsigned int x)
{
#ifdef __GNUC__
return 1 << (sizeof(unsigned int) * 8 - __builtin_clz(--x));
#else
x--;
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return ++x;
#endif
}
/**
* @brief Count bits set
* @param w Number in which to count bits
* @return The number of bits set
*
* Counts the number of bits in an unsigned int
* that are set to 1. So, for example, in the
* number 5, which is 101 in binary, there are
* two bits set to 1.
*/
static inline unsigned int count_bits_set(unsigned int w)
{
#ifdef __GNUC__
return __builtin_popcount(w);
#else
const int S[] = {1, 2, 4, 8, 16};
const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
int c = w;
c = ((c >> S[0]) & B[0]) + (c & B[0]);
c = ((c >> S[1]) & B[1]) + (c & B[1]);
c = ((c >> S[2]) & B[2]) + (c & B[2]);
c = ((c >> S[3]) & B[3]) + (c & B[3]);
c = ((c >> S[4]) & B[4]) + (c & B[4]);
return c;
#endif
}
static inline unsigned count_leading_ones(unsigned int x)
{
unsigned int i = ((~x) << 24) | 0x00FFFFFF;
#ifdef _MSC_VER
unsigned long r;
_BitScanReverse(&r, (unsigned long)i);
return 31 - r;
#else
return __builtin_clz(i);
#endif
}
/**
* quote from GCC doc "Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero."
*/
static inline unsigned bits_ffs(unsigned int x)
{
#ifdef __GNUC__
return __builtin_ffs(x);
#else
if (x == 0) return 0;
unsigned i = 1;
while (!(x & 0x1)) {
x = x >> 1;
++i;
}
return i;
#endif
}
/**
* @brief Make even number macro
* @param n Number to make even
*
* Quick macro to make a number even, by
* forcing the rightmost bit to 0.
*/
#define make_even_number(n) ((n) += ((n) & 0x1)?1:0) //! ~ceil()
//#define make_even_number(n) ((x) &= ~0x1) //! ~floor()
/**
* @brief Conditionally set flag macro
* @param number to set or unset flag in
* @param mask bitmask to be set or unset
* @param condition whether to set or unset the flag
*
* According to a condition, this macro will set or unset a
* particular flag in a number. It's a quick way of doing
* this:
* if (condition) number |= mask; else number &= ~mask;
*/
#define conditionally_set_flag(number, mask, condition) ((number) ^= (-(condition) ^ (number)) & (mask))
#endif /* _BITOPS_H */
|
