-
Notifications
You must be signed in to change notification settings - Fork 0
/
branchless.h
162 lines (133 loc) · 3.91 KB
/
branchless.h
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <stdint.h>
#include <stdbool.h>
#ifndef BRANCHLESS_H
#define BRANCHLESS_H
/**
* gets the sign of the number
*
* @param x number to check
* @return 1 for positive number or zero, 0 for negative
* @link http://www.coranac.com/documents/bittrick/#ssec-math-sign2
*/
int32_t positive_sign(int32_t x);
/**
* gets the sign of the number
*
* @param x number to check
* @return 0 for positive number or zero, -1 for negative
* @link http://www.coranac.com/documents/bittrick/#ssec-math-sign2
*/
int32_t negative_sign(int32_t x);
/**
* gets the sign of the number
*
* @param x number to check
* @return 1 for positive number or zero, -1 for negative
* @link http://www.coranac.com/documents/bittrick/#ssec-math-sign2
*/
int32_t sign_sign(int32_t x);
/**
* gets the sign of the number
*
* @param x number to check
* @return 1 for positive number, -1 for negative and 0 for zero
* @link http://www.coranac.com/documents/bittrick/#ssec-math-sign3
*/
int32_t sign_sign_zero(int32_t x);
/**
* checks if the value is a power of 2
*
* @param x value to check
* @return true if value is a power of 2, false otherwise
* @link http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
*/
bool is_power_of_2_int32(int32_t x);
bool is_power_of_2_int64(int64_t x);
/**
* checks whether provided values have different signs
*
* @param x first value
* @param y second value
* @return true if opposite signs, false if same
* @link http://graphics.stanford.edu/~seander/bithacks.html#DetectOppositeSigns
* @author Manfred Weis
*/
bool opposite_sign_int32(int32_t x, int32_t y);
bool opposite_sign_int64(int64_t x, int64_t y);
/**
* @link http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs
* @author Peter Kankowski
*/
int32_t abs_int32(int32_t x);
int64_t abs_int64(int64_t x);
/**
* @link http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
* @author Timothy B. Terriberry
*/
int32_t min_int32(int32_t x, int32_t y);
int32_t max_int32(int32_t x, int32_t y);
int64_t min_int64(int64_t x, int64_t y);
int64_t max_int64(int64_t x, int64_t y);
/**
* @link http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
* @author Don Clugston
*/
int32_t count_bits_int32(int32_t x);
int64_t count_bits_int64(int64_t x);
#endif //BRANCHLESS_H
#ifdef BRANCHLESS_IMPLEMENTATION
inline int32_t negative_sign(int32_t x) {
return x >> 31;
}
inline int32_t positive_sign(int32_t x) {
return (x >> 31) + 1;
}
inline int32_t sign_sign(int32_t x) {
return (x >> 31) | 1;
}
inline int32_t sign_sign_zero(int32_t x) {
return (x >> 31) - (-x >> 31);
}
inline bool is_power_of_2_int32(int32_t x) {
return x && !(x & (x - 1));
}
inline bool is_power_of_2_int64(int64_t x) {
return x && !(x & (x - 1));
}
inline int32_t abs_int32(int32_t x) {
int32_t mask = x >> 31;
return (x + mask) ^ mask;
}
inline int64_t abs_int64(int64_t x) {
int64_t mask = x >> 63;
return (x + mask) ^ mask;
}
inline bool opposite_sign_int32(int32_t x, int32_t y) {
return (x ^ y) < 0;
}
inline bool opposite_sign_int64(int64_t x, int64_t y) {
return (x ^ y) < 0;
}
inline int32_t min_int32(int32_t x, int32_t y) {
return y ^ ((x ^ y) & -(x < y));
}
inline int32_t max_int32(int32_t x, int32_t y) {
return x ^ ((x ^ y) & -(x < y));
}
inline int64_t min_int64(int64_t x, int64_t y) {
return y ^ ((x ^ y) & -(x < y));
}
inline int64_t max_int64(int64_t x, int64_t y) {
return x ^ ((x ^ y) & -(x < y));
}
inline int32_t count_bits_int32(int32_t x) {
x -= (x >> 1) & 0x55555555;
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
return ((x + (x >> 4) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
inline int64_t count_bits_int64(int64_t x) {
x -= (x >> 1) & 0x5555555555555555;
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
return ((x + (x >> 4) & 0x0F0F0F0F0F0F0F0F) * 0x0101010101010101) >> 56;
}
#endif //BRANCHLESS_IMPLEMENTATION