-
Notifications
You must be signed in to change notification settings - Fork 3
/
Bitwise Twiddling Tricks.c
executable file
·155 lines (129 loc) · 2.91 KB
/
Bitwise Twiddling Tricks.c
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
/**
* BIT TWIDDLING TRICKS
* ==============================================
*/
/**
10 - 2
100 - 4
1000 - 8
10000 - 16
100000 - 32
1000000 - 64
10000000 - 128
etc...
**/
/** Extract/Test the first bit from the integer **/
// Example:
int k = 13;
printf("%d", k & 1); // This will extract the 0th bit from the k
// Explaination
/**
* 13 is 1101
* 0001
* ------
* 0001 // This will extract the 0th bit
*/
/** Determine if number is even or odd **/
// Example:
if((n & 1) == 0)
printf("even");
else
printf("odd");
// Explanation
/**
* As before, it will extract the first bit, and by this bit we can know that if number is even or odd
* Because only 0th bit will determine (if it is 1 then odd, else even). Think?
*/
/** Extract/Test the nth bit from the integer **/
// Example:
if(x & (1 << n))
printf("nth-bit is 1");
else
printf("nth-bit is 0");
// Explanation:
/**
* 13 is 1101. And we have to check 2nd bit, so 13 & (1 << 2)
* 1101
* 100
* ------
* 0100
* ------
* So, 2nd bit is 1 or we can say 2nd bit is set
*/
/** Set the nth-bit i.e., make it 1 **/
// Example:
int y = x | (1 << n)
// Explanation:
/**
* 13 is 1101. And we have to set 2nd bit, so 13 | (1 << 2)
* 1101
* 100
* -----
* 1101 // No change, bet 2nd bit already on (or 1)
*
* Now, try for 1st bit, so 13 & (1 << 1)
* 1101
* 10
* ----
* 1111 // Now 1st bit is ON
*/
// If otherwise, we want to set it to zero if it already set to 1. then we XOR(^) operator. eg: 13 ^ (1 << n).
// This is also called toggling of bit (x ^ (1 << n))
/** Unset the nth-bit. i.e., Turns on all the bits except nth-bit **/
// Example:
int y = x & ~(1<<n)
// Explanation:
/**
01111111 (127 in decimal)
& 11101111 (~(1<<4))
--------
01101111
**/
/** Turn off the rightmost (i.e., first 1 bit from the right) 1-bit in a word, producing 0 if none **/
// Formula:
int y = x & (x-1)
/** Example
1011000 (88 in decimal)
& (1011000
- 0000001)
-------
1010000
**/
/** Turn off the rightmost 0-bit in a word **/
// Formula
int y = x | (x + 1)
/** Example
1101
+ 1
----
1110
& 1101
----
1100
----
Adding `1` to any word, transform righmost 1's in a zero and first rightmost 0 in a 1.
**/
/**
* Basic Theorems
*/
// De-morgan's law (first two)
(X & Y & Z ...)` == X` | Y` | Z` ... // Eg: ~(x & y) = ~x | ~y
(X | Y | Z ...)` == X` & Y` & Z` ... // Eg: ~(x | y) = ~x & ~y
~(x + 1) = ~x - 1
~(x - 1) = ~x + 1
~(x^y) = ~x^y
~-x = x - 1
-~x = x + 1
~(x + y) = ~x - y
~(x - y) = ~x + y
-x = ~x + 1 = ~(x - 1)
~x = -x - 1
x + y = x - ~y - 1
= (x ^ y) + 2(x & y)
= (x | y) + (x & y)
= 2(x | y) - (x ^ y)
x - y = x + ~y + 1
= (x ^ y) - 2(~x & y)
= (x & ~y) - (~x & y)
= 2(x & ~y) - (x ^ y)
x^y = (x | y) - (x & y)