Skip to content

Instantly share code, notes, and snippets.

@graphitemaster

graphitemaster/bit_hacks.c

Created April 5, 2012 05:42
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save graphitemaster/2308278 to your computer and use it in GitHub Desktop.
Save graphitemaster/2308278 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
bit_hacks.c
/*
* Bit twiddling hacks: By Dale Weiler (a.k.a graphitemaster)
* all code is public domain.
*/
#include <limits.h>
#include <stdio.h>
/*
* Simple utility to convert integer to binary string: it's a pity
* C doesn't support a format specifier for printf. Or binary constants
* they're GCC extensions.
*/
char *itob(int x) {
static char b [sizeof(int) * CHAR_BIT + 1];
int i,j= sizeof(int) * CHAR_BIT - 1;
b[j] =0;
for(i=0; i< sizeof(int) * CHAR_BIT; i++)
b[--j] = (x & (1 << i))?'1':'0';
return b;
}
/*
* Test if divisible by 5 without using modulus
* this works because 0xCCCCCCCD is the inverse of 5 modulo 2^32
* where (x*0xCCCCCCCD) is expanded with bitwise ops below
*
* this is slow:
* for example on a pentium 4 which lacks a barrel shifter,
* each of these bits that are shifting costs 1 cycle.
* There is a much better version below which is faster
* than modulus (x%5), and this.
*/
int div5(unsigned x) {
return ((x<<0x1F)+(x<<0x1E)+(x<<0x1B)+(x<<0x1A)+
(x<<0x17)+(x<<0x16)+(x<<0x13)+(x<<0x12)+
(x<<0x0F)+(x<<0x0E)+(x<<0x0B)+(x<<0x0A)+
(x<<0x07)+(x<<0x06)+(x<<0x03)+(x<<0x02)+x < 0x33333334);
}
/*
* alternitive version of this function (much faster):
* MUL is generally the most efficient way to do division
* by non-powers-of-two constants. (faster than modulus too)
*/
int div5_mul(unsigned x) {
return (x * 0xCCCCCCCD) < 0x33333334;
}
/*
* We can extend the check for divisible by 5 to determine
* if something is divisible by 10 just by checking if it's
* divisble by 5 as well as 2.
*/
int div10(unsigned x) {
return div5(x) && (x&1) == 0;
}
/* We can also use div5_mul to speed it up */
int div10_mul(unsigned x) {
return div5_mul(x) && (x&1) == 0;
}
/*
* Of course we can also do this a few other ways
* such as: (all single expressions)
*/
int div10_wow(unsigned x) {
return !((0x19999999 * x + (x >> 1) + (x >> 3)) >> 28)[
"\0x0\0x1\0x2\0x2\0x3\0x3\0x4\0x5\0x5\0x6\0x7\0x7\0x8\0x8\0x9\0x0"
];
}
/* Slighly faster then above */
int div10_nop(unsigned x) {
return ((0x04432210 >> (((0x33333333 * x + (x >> 3)) >> 29) << 2)) & 7);
}
/*
* We can also do it a different way (for 7) knowing that
* x%7 = ((R1%7)*(64%7) + (R2%7)*(8%7) + R3%7) % 7
* simplify:
* (R1%7 + R2%7 + R3%7) % 7
* (R1 + R2 + R3) % 7
*
* because 64%7 = 8%7 = 1
*
* for:
* R1 = (X>>6)&7
* R2 = (X>>3)&7
* R3 = X&7
*
* the maximum value would be 7+7+3 or 17
*/
int div7(unsigned x) {
x = (x&7) + ((x>>3)&7) + (x>>6);
x = (x&7) + (x>>3);
return x==7;
}
/*
* Of course like all others we can make it a single expression
* as well. This is a lot slower than div7 above. More shifts
* are used here to allow single expression.
*/
int div7_single(unsigned x) {
return ((x&7)+((x>>3)&7)+(x>>6)&7)+((x&7)+((x>>3)&7)+(x>>6)>>3)==7;
}
int main() {
int i;
for(i=0; i < 200; i++)
printf("% 8d %s -- 5:%s, 7:%s, 10:%s, \n", i, itob(i), div5(i)?"pass":"fail", div7(i)?"pass":"fail", div10(i)?"pass":"fail");
}
/* Output:
0 0000000000000000000000000000000 -- 5:pass, 7:fail, 10:pass,
1 0000000000000000000000000000001 -- 5:fail, 7:fail, 10:fail,
2 0000000000000000000000000000010 -- 5:fail, 7:fail, 10:fail,
3 0000000000000000000000000000011 -- 5:fail, 7:fail, 10:fail,
4 0000000000000000000000000000100 -- 5:fail, 7:fail, 10:fail,
5 0000000000000000000000000000101 -- 5:pass, 7:fail, 10:fail,
6 0000000000000000000000000000110 -- 5:fail, 7:fail, 10:fail,
7 0000000000000000000000000000111 -- 5:fail, 7:pass, 10:fail,
8 0000000000000000000000000001000 -- 5:fail, 7:fail, 10:fail,
9 0000000000000000000000000001001 -- 5:fail, 7:fail, 10:fail,
10 0000000000000000000000000001010 -- 5:pass, 7:fail, 10:pass,
11 0000000000000000000000000001011 -- 5:fail, 7:fail, 10:fail,
12 0000000000000000000000000001100 -- 5:fail, 7:fail, 10:fail,
13 0000000000000000000000000001101 -- 5:fail, 7:fail, 10:fail,
14 0000000000000000000000000001110 -- 5:fail, 7:pass, 10:fail,
15 0000000000000000000000000001111 -- 5:pass, 7:fail, 10:fail,
16 0000000000000000000000000010000 -- 5:fail, 7:fail, 10:fail,
17 0000000000000000000000000010001 -- 5:fail, 7:fail, 10:fail,
18 0000000000000000000000000010010 -- 5:fail, 7:fail, 10:fail,
19 0000000000000000000000000010011 -- 5:fail, 7:fail, 10:fail,
20 0000000000000000000000000010100 -- 5:pass, 7:fail, 10:pass,
21 0000000000000000000000000010101 -- 5:fail, 7:pass, 10:fail,
22 0000000000000000000000000010110 -- 5:fail, 7:fail, 10:fail,
23 0000000000000000000000000010111 -- 5:fail, 7:fail, 10:fail,
24 0000000000000000000000000011000 -- 5:fail, 7:fail, 10:fail,
25 0000000000000000000000000011001 -- 5:pass, 7:fail, 10:fail,
26 0000000000000000000000000011010 -- 5:fail, 7:fail, 10:fail,
27 0000000000000000000000000011011 -- 5:fail, 7:fail, 10:fail,
28 0000000000000000000000000011100 -- 5:fail, 7:pass, 10:fail,
29 0000000000000000000000000011101 -- 5:fail, 7:fail, 10:fail,
30 0000000000000000000000000011110 -- 5:pass, 7:fail, 10:pass,
31 0000000000000000000000000011111 -- 5:fail, 7:fail, 10:fail,
32 0000000000000000000000000100000 -- 5:fail, 7:fail, 10:fail,
33 0000000000000000000000000100001 -- 5:fail, 7:fail, 10:fail,
34 0000000000000000000000000100010 -- 5:fail, 7:fail, 10:fail,
35 0000000000000000000000000100011 -- 5:pass, 7:pass, 10:fail,
36 0000000000000000000000000100100 -- 5:fail, 7:fail, 10:fail,
37 0000000000000000000000000100101 -- 5:fail, 7:fail, 10:fail,
38 0000000000000000000000000100110 -- 5:fail, 7:fail, 10:fail,
39 0000000000000000000000000100111 -- 5:fail, 7:fail, 10:fail,
40 0000000000000000000000000101000 -- 5:pass, 7:fail, 10:pass,
41 0000000000000000000000000101001 -- 5:fail, 7:fail, 10:fail,
42 0000000000000000000000000101010 -- 5:fail, 7:pass, 10:fail,
43 0000000000000000000000000101011 -- 5:fail, 7:fail, 10:fail,
44 0000000000000000000000000101100 -- 5:fail, 7:fail, 10:fail,
45 0000000000000000000000000101101 -- 5:pass, 7:fail, 10:fail,
46 0000000000000000000000000101110 -- 5:fail, 7:fail, 10:fail,
47 0000000000000000000000000101111 -- 5:fail, 7:fail, 10:fail,
48 0000000000000000000000000110000 -- 5:fail, 7:fail, 10:fail,
49 0000000000000000000000000110001 -- 5:fail, 7:pass, 10:fail,
50 0000000000000000000000000110010 -- 5:pass, 7:fail, 10:pass,
51 0000000000000000000000000110011 -- 5:fail, 7:fail, 10:fail,
52 0000000000000000000000000110100 -- 5:fail, 7:fail, 10:fail,
53 0000000000000000000000000110101 -- 5:fail, 7:fail, 10:fail,
54 0000000000000000000000000110110 -- 5:fail, 7:fail, 10:fail,
55 0000000000000000000000000110111 -- 5:pass, 7:fail, 10:fail,
56 0000000000000000000000000111000 -- 5:fail, 7:pass, 10:fail,
57 0000000000000000000000000111001 -- 5:fail, 7:fail, 10:fail,
58 0000000000000000000000000111010 -- 5:fail, 7:fail, 10:fail,
59 0000000000000000000000000111011 -- 5:fail, 7:fail, 10:fail,
60 0000000000000000000000000111100 -- 5:pass, 7:fail, 10:pass,
61 0000000000000000000000000111101 -- 5:fail, 7:fail, 10:fail,
62 0000000000000000000000000111110 -- 5:fail, 7:fail, 10:fail,
63 0000000000000000000000000111111 -- 5:fail, 7:pass, 10:fail,
64 0000000000000000000000001000000 -- 5:fail, 7:fail, 10:fail,
65 0000000000000000000000001000001 -- 5:pass, 7:fail, 10:fail,
66 0000000000000000000000001000010 -- 5:fail, 7:fail, 10:fail,
67 0000000000000000000000001000011 -- 5:fail, 7:fail, 10:fail,
68 0000000000000000000000001000100 -- 5:fail, 7:fail, 10:fail,
69 0000000000000000000000001000101 -- 5:fail, 7:fail, 10:fail,
70 0000000000000000000000001000110 -- 5:pass, 7:pass, 10:pass,
71 0000000000000000000000001000111 -- 5:fail, 7:fail, 10:fail,
72 0000000000000000000000001001000 -- 5:fail, 7:fail, 10:fail,
73 0000000000000000000000001001001 -- 5:fail, 7:fail, 10:fail,
74 0000000000000000000000001001010 -- 5:fail, 7:fail, 10:fail,
75 0000000000000000000000001001011 -- 5:pass, 7:fail, 10:fail,
76 0000000000000000000000001001100 -- 5:fail, 7:fail, 10:fail,
77 0000000000000000000000001001101 -- 5:fail, 7:pass, 10:fail,
78 0000000000000000000000001001110 -- 5:fail, 7:fail, 10:fail,
79 0000000000000000000000001001111 -- 5:fail, 7:fail, 10:fail,
80 0000000000000000000000001010000 -- 5:pass, 7:fail, 10:pass,
81 0000000000000000000000001010001 -- 5:fail, 7:fail, 10:fail,
82 0000000000000000000000001010010 -- 5:fail, 7:fail, 10:fail,
83 0000000000000000000000001010011 -- 5:fail, 7:fail, 10:fail,
84 0000000000000000000000001010100 -- 5:fail, 7:pass, 10:fail,
85 0000000000000000000000001010101 -- 5:pass, 7:fail, 10:fail,
86 0000000000000000000000001010110 -- 5:fail, 7:fail, 10:fail,
87 0000000000000000000000001010111 -- 5:fail, 7:fail, 10:fail,
88 0000000000000000000000001011000 -- 5:fail, 7:fail, 10:fail,
89 0000000000000000000000001011001 -- 5:fail, 7:fail, 10:fail,
90 0000000000000000000000001011010 -- 5:pass, 7:fail, 10:pass,
91 0000000000000000000000001011011 -- 5:fail, 7:pass, 10:fail,
92 0000000000000000000000001011100 -- 5:fail, 7:fail, 10:fail,
93 0000000000000000000000001011101 -- 5:fail, 7:fail, 10:fail,
94 0000000000000000000000001011110 -- 5:fail, 7:fail, 10:fail,
95 0000000000000000000000001011111 -- 5:pass, 7:fail, 10:fail,
96 0000000000000000000000001100000 -- 5:fail, 7:fail, 10:fail,
97 0000000000000000000000001100001 -- 5:fail, 7:fail, 10:fail,
98 0000000000000000000000001100010 -- 5:fail, 7:pass, 10:fail,
99 0000000000000000000000001100011 -- 5:fail, 7:fail, 10:fail,
100 0000000000000000000000001100100 -- 5:pass, 7:fail, 10:pass,
101 0000000000000000000000001100101 -- 5:fail, 7:fail, 10:fail,
102 0000000000000000000000001100110 -- 5:fail, 7:fail, 10:fail,
103 0000000000000000000000001100111 -- 5:fail, 7:fail, 10:fail,
104 0000000000000000000000001101000 -- 5:fail, 7:fail, 10:fail,
105 0000000000000000000000001101001 -- 5:pass, 7:pass, 10:fail,
106 0000000000000000000000001101010 -- 5:fail, 7:fail, 10:fail,
107 0000000000000000000000001101011 -- 5:fail, 7:fail, 10:fail,
108 0000000000000000000000001101100 -- 5:fail, 7:fail, 10:fail,
109 0000000000000000000000001101101 -- 5:fail, 7:fail, 10:fail,
110 0000000000000000000000001101110 -- 5:pass, 7:fail, 10:pass,
111 0000000000000000000000001101111 -- 5:fail, 7:fail, 10:fail,
112 0000000000000000000000001110000 -- 5:fail, 7:pass, 10:fail,
113 0000000000000000000000001110001 -- 5:fail, 7:fail, 10:fail,
114 0000000000000000000000001110010 -- 5:fail, 7:fail, 10:fail,
115 0000000000000000000000001110011 -- 5:pass, 7:fail, 10:fail,
116 0000000000000000000000001110100 -- 5:fail, 7:fail, 10:fail,
117 0000000000000000000000001110101 -- 5:fail, 7:fail, 10:fail,
118 0000000000000000000000001110110 -- 5:fail, 7:fail, 10:fail,
119 0000000000000000000000001110111 -- 5:fail, 7:pass, 10:fail,
120 0000000000000000000000001111000 -- 5:pass, 7:fail, 10:pass,
121 0000000000000000000000001111001 -- 5:fail, 7:fail, 10:fail,
122 0000000000000000000000001111010 -- 5:fail, 7:fail, 10:fail,
123 0000000000000000000000001111011 -- 5:fail, 7:fail, 10:fail,
124 0000000000000000000000001111100 -- 5:fail, 7:fail, 10:fail,
125 0000000000000000000000001111101 -- 5:pass, 7:fail, 10:fail,
126 0000000000000000000000001111110 -- 5:fail, 7:pass, 10:fail,
127 0000000000000000000000001111111 -- 5:fail, 7:fail, 10:fail,
128 0000000000000000000000010000000 -- 5:fail, 7:fail, 10:fail,
129 0000000000000000000000010000001 -- 5:fail, 7:fail, 10:fail,
130 0000000000000000000000010000010 -- 5:pass, 7:fail, 10:pass,
131 0000000000000000000000010000011 -- 5:fail, 7:fail, 10:fail,
132 0000000000000000000000010000100 -- 5:fail, 7:fail, 10:fail,
133 0000000000000000000000010000101 -- 5:fail, 7:pass, 10:fail,
134 0000000000000000000000010000110 -- 5:fail, 7:fail, 10:fail,
135 0000000000000000000000010000111 -- 5:pass, 7:fail, 10:fail,
136 0000000000000000000000010001000 -- 5:fail, 7:fail, 10:fail,
137 0000000000000000000000010001001 -- 5:fail, 7:fail, 10:fail,
138 0000000000000000000000010001010 -- 5:fail, 7:fail, 10:fail,
139 0000000000000000000000010001011 -- 5:fail, 7:fail, 10:fail,
140 0000000000000000000000010001100 -- 5:pass, 7:pass, 10:pass,
141 0000000000000000000000010001101 -- 5:fail, 7:fail, 10:fail,
142 0000000000000000000000010001110 -- 5:fail, 7:fail, 10:fail,
143 0000000000000000000000010001111 -- 5:fail, 7:fail, 10:fail,
144 0000000000000000000000010010000 -- 5:fail, 7:fail, 10:fail,
145 0000000000000000000000010010001 -- 5:pass, 7:fail, 10:fail,
146 0000000000000000000000010010010 -- 5:fail, 7:fail, 10:fail,
147 0000000000000000000000010010011 -- 5:fail, 7:pass, 10:fail,
148 0000000000000000000000010010100 -- 5:fail, 7:fail, 10:fail,
149 0000000000000000000000010010101 -- 5:fail, 7:fail, 10:fail,
150 0000000000000000000000010010110 -- 5:pass, 7:fail, 10:pass,
151 0000000000000000000000010010111 -- 5:fail, 7:fail, 10:fail,
152 0000000000000000000000010011000 -- 5:fail, 7:fail, 10:fail,
153 0000000000000000000000010011001 -- 5:fail, 7:fail, 10:fail,
154 0000000000000000000000010011010 -- 5:fail, 7:pass, 10:fail,
155 0000000000000000000000010011011 -- 5:pass, 7:fail, 10:fail,
156 0000000000000000000000010011100 -- 5:fail, 7:fail, 10:fail,
157 0000000000000000000000010011101 -- 5:fail, 7:fail, 10:fail,
158 0000000000000000000000010011110 -- 5:fail, 7:fail, 10:fail,
159 0000000000000000000000010011111 -- 5:fail, 7:fail, 10:fail,
160 0000000000000000000000010100000 -- 5:pass, 7:fail, 10:pass,
161 0000000000000000000000010100001 -- 5:fail, 7:pass, 10:fail,
162 0000000000000000000000010100010 -- 5:fail, 7:fail, 10:fail,
163 0000000000000000000000010100011 -- 5:fail, 7:fail, 10:fail,
164 0000000000000000000000010100100 -- 5:fail, 7:fail, 10:fail,
165 0000000000000000000000010100101 -- 5:pass, 7:fail, 10:fail,
166 0000000000000000000000010100110 -- 5:fail, 7:fail, 10:fail,
167 0000000000000000000000010100111 -- 5:fail, 7:fail, 10:fail,
168 0000000000000000000000010101000 -- 5:fail, 7:pass, 10:fail,
169 0000000000000000000000010101001 -- 5:fail, 7:fail, 10:fail,
170 0000000000000000000000010101010 -- 5:pass, 7:fail, 10:pass,
171 0000000000000000000000010101011 -- 5:fail, 7:fail, 10:fail,
172 0000000000000000000000010101100 -- 5:fail, 7:fail, 10:fail,
173 0000000000000000000000010101101 -- 5:fail, 7:fail, 10:fail,
174 0000000000000000000000010101110 -- 5:fail, 7:fail, 10:fail,
175 0000000000000000000000010101111 -- 5:pass, 7:pass, 10:fail,
176 0000000000000000000000010110000 -- 5:fail, 7:fail, 10:fail,
177 0000000000000000000000010110001 -- 5:fail, 7:fail, 10:fail,
178 0000000000000000000000010110010 -- 5:fail, 7:fail, 10:fail,
179 0000000000000000000000010110011 -- 5:fail, 7:fail, 10:fail,
180 0000000000000000000000010110100 -- 5:pass, 7:fail, 10:pass,
181 0000000000000000000000010110101 -- 5:fail, 7:fail, 10:fail,
182 0000000000000000000000010110110 -- 5:fail, 7:pass, 10:fail,
183 0000000000000000000000010110111 -- 5:fail, 7:fail, 10:fail,
184 0000000000000000000000010111000 -- 5:fail, 7:fail, 10:fail,
185 0000000000000000000000010111001 -- 5:pass, 7:fail, 10:fail,
186 0000000000000000000000010111010 -- 5:fail, 7:fail, 10:fail,
187 0000000000000000000000010111011 -- 5:fail, 7:fail, 10:fail,
188 0000000000000000000000010111100 -- 5:fail, 7:fail, 10:fail,
189 0000000000000000000000010111101 -- 5:fail, 7:pass, 10:fail,
190 0000000000000000000000010111110 -- 5:pass, 7:fail, 10:pass,
191 0000000000000000000000010111111 -- 5:fail, 7:fail, 10:fail,
192 0000000000000000000000011000000 -- 5:fail, 7:fail, 10:fail,
193 0000000000000000000000011000001 -- 5:fail, 7:fail, 10:fail,
194 0000000000000000000000011000010 -- 5:fail, 7:fail, 10:fail,
195 0000000000000000000000011000011 -- 5:pass, 7:fail, 10:fail,
196 0000000000000000000000011000100 -- 5:fail, 7:pass, 10:fail,
197 0000000000000000000000011000101 -- 5:fail, 7:fail, 10:fail,
198 0000000000000000000000011000110 -- 5:fail, 7:fail, 10:fail,
199 0000000000000000000000011000111 -- 5:fail, 7:fail, 10:fail,
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment