[mascara-docs.git] / lang / C / the.ansi.c.programming.language / c.programming.notes.int / sx4ab.html
| blob | 31811f3e022ad6a7089edb6b0f3e29ed223c6686 |
2 <!-- This collection of hypertext pages is Copyright 1995-7 by Steve Summit. -->
3 <!-- This material may be freely redistributed and used -->
4 <!-- but may not be republished or sold without permission. -->
5 <html>
6 <head>
13 </head>
14 <body>
18 </p><p>The bitwise operators operate on numbers
19 (always integers)
20 as if they were
21 sequences
22 of binary bits
23 (which, of course, internally to the computer they
24 are).
25 These operators will make the most sense,
26 therefore,
27 if we consider integers as represented in binary, octal, or hexadecimal
29 not decimal (base 10).
30 Remember,
32 you can use octal constants in C
34 and you can use hexadecimal constants
38 performs a bitwise AND on two integers.
39 Each bit in the result is 1 only if
40 both corresponding bits in the two input operands are 1.
42 because (in binary):
43 <pre>
44 0 1 0 1 0 1 1 0
46 ---------------
47 0 0 0 1 0 0 1 0
48 </pre>
50 performs a bitwise OR on two integers.
51 Each bit in the result is 1 if
52 either of the corresponding bits in the two input operands is 1.
54 because:
55 <pre>
56 0 1 0 1 0 1 1 0
57 | 0 0 1 1 0 0 1 0
58 ---------------
59 0 1 1 1 0 1 1 0
60 </pre>
62 performs a bitwise exclusive-OR on two integers.
63 Each bit in the result is 1 if
64 one, but not both,
65 of the corresponding bits in the two input operands is 1.
67 <pre>
68 0 1 0 1 0 1 1 0
69 ^ 0 0 1 1 0 0 1 0
70 ---------------
71 0 1 1 0 0 1 0 0
72 </pre>
74 performs a bitwise complement on its single integer operand.
78 Complementing a number means to change all the
82 <pre>
83 ~ 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0
84 -------------------------------
85 1 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1
86 </pre>
88 shifts its first operand left by a number of bits
89 given by its second operand,
90 filling in new 0 bits at the right.
92 shifts its first operand right.
95 but if the first operand is signed,
97 (Uncertainty like this
98 is one reason why it's usually a good idea
100 when working with the bitwise operators.)
102 <pre>
104 -------------------
105 0 1 0 1 0 1 1 0 0 0
106 </pre>
108 <pre>
110 ---------------
111 0 1 0 1 0 1 1
112 </pre>
113 For both of the shift operators,
114 bits that scroll ``off the end'' are discarded;
115 they don't wrap around.
117 </p><p>The bitwise operators will make more sense
118 if we take a look at some of the ways they're typically used.
122 <pre>
123 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 0
125 --------------- ---------------
126 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
127 </pre>
128 Since any nonzero result is considered ``true'' in C,
130 to test some condition,
131 for example:
132 <pre>
135 </pre>
136 (If we didn't like testing against the bitwise result,
137 we could equivalently say
139 The extra parentheses are important, as we'll explain below.)
140 </p><p>Notice that
142 has exactly one 1 bit in its binary representation,
143 which makes it useful for testing
144 for the presence of a certain bit.
145 Such a value
147 Often, we'll define a series of bit masks,
148 all targeting different bits,
150 A ``flag'' is an on-off, yes-no condition,
154 does more than just save space,
155 it also makes it convenient to assign a set of flags all at once
156 from one flag variable to another,
158 For example, if we made these definitions:
159 <pre>
160 #define DIRTY 0x01
161 #define OPEN 0x02
162 #define VERBOSE 0x04
163 #define RED 0x08
164 #define SEASICK 0x10
165 </pre>
166 we would have set up 5 different bits
167 as keeping track of those 5 different conditions
168 (``dirty,'' ``open,'' etc.).
169 If we had a variable
170 <pre>
171 unsigned int flags;
172 </pre>
173 which contained a set of these flags,
174 we could write tests like
175 <pre>
176 if(flags & DIRTY)
177 { /* code for dirty case */ }
178 </pre>
179 <pre>
180 if(!(flags & OPEN))
181 { /* code for closed case */ }
182 </pre>
183 <pre>
184 if(flags & VERBOSE)
185 { /* code for verbose case */ }
186 else { /* code for quiet case */ }
187 </pre>
189 can be read as
193 we'd say
194 <pre>
195 flags = flags | DIRTY; /* set DIRTY bit */
196 </pre>
197 How would we ``turn off'' a bit?
198 The way to do it is to leave on every bit but the one we're turning off,
199 if they were on already.
201 <pre>
202 flags = flags & ~DIRTY; /* clear DIRTY bit */
203 </pre>
204 This may be easier to see if we look at it in binary.
206 were already on,
208 <pre>
209 0 0 0 1 1 0 0 1
211 ---------------
212 0 0 0 1 1 0 0 0
213 </pre>
214 As you can see,
217 have no effect if the targeted bit were already on or off, respectively.
218 </p><p>The definition of the exclusive-OR operator
220 that is,
222 <pre>
223 flags = flags ^ VERBOSE; /* toggle VERBOSE bit */
224 </pre>
226 when doing all of these operations:
227 <pre>
228 flags |= DIRTY; /* set DIRTY bit */
229 flags &= ~OPEN; /* clear OPEN bit */
230 flags ^= VERBOSE; /* toggle VERBOSE bit */
231 </pre>
232 </p><p>We can also use the bitwise operators to extract
233 subsets of bits from the middle of
234 an integer.
235 For example,
236 to extract the second-to-last hexadecimal ``digit,''
237 we could use
238 <pre>
240 </pre>
242 <pre>
243 i 0 1 0 1 0 1 1 0
245 ---------------
246 0 1 0 1 0 0 0 0
247 </pre>
248 and shifting this result right by 4 bits
250 or 5,
251 as we wished.
252 Replacing
253 (or overwriting)
254 a subset of bits
255 is a bit more complicated;
257 to clear all of the destination bits,
259 the new bits.
260 For example,
261 to replace that second-to-last hexadecimal digit
262 with some new bits,
263 we might use:
264 <pre>
266 </pre>
268 this would give us
269 <pre>
270 i 0 1 0 1 0 1 1 0
272 ---------------
273 0 0 0 0 0 1 1 0
275 ---------------
276 0 1 1 0 0 1 1 0
277 </pre>
279 </p><p>We've been using extra parentheses
280 in several of these bitwise expressions
281 because it turns out that
282 (for the usual, hoary sort of ``historical reasons'')
283 the precedence of
285 operators is low, usually lower than we'd want.
286 (The reason that they're low is that, once upon a time,
293 expressions like
294 <pre>
296 </pre>
297 and
298 <pre>
300 </pre>
302 these last two would be equivalent to
303 <pre>
306 </pre>
307 and would not do the bit test or subset extraction that we wanted.
308 </p><p>[The rest of this section is somewhat advanced and may be skipped.]
310 it turns out that shifting left and shifting right
311 are equivalent to multiplying and dividing by two.
312 These operations are equivalent for the same reason that
313 tacking zeroes on to the right of a number in base 10
314 is the same as multiplying by 10,
315 and deleting digits from the right is the same as dividing by 10.
316 You can convince yourself that
319 and that
322 It's also the case that masking off all but the low-order bits
323 is the same as taking a remainder;
324 for example,
327 Some programmers therefore use
329 in preference to
331 when powers of two are involved,
332 on the grounds that the bitwise operators are ``more efficient.''
333 Usually it isn't worth worrying about this, though,
334 because most compilers are smart enough
335 to perform these optimizations anyway
337 the compiler might generate a left shift instruction all by itself),
338 they're not always as readable,
339 and they're not always correct for negative numbers.
340 </p><p>The issue of negative numbers, by the way,
342 is not precisely defined
343 when the high-order bit of the value being shifted is 1.
344 For signed values,
345 if the high-order bit is a 1,
346 the number is negative.
348 and sign-magnitude representations.)
349 If you were using a right shift to implement division,
350 you'd want a negative number to stay negative,
351 so on some computers,
352 under some compilers,
353 when you shift a signed value right
354 and the high-order bit is 1,
355 new
357 However, you can't depend on this,
358 because not all computers and compilers implement right shift this way.
359 In any case,
360 shifting negative numbers to the right
361 (even if the high-order 1 bit propagates)
362 gives you an incorrect answer if there's a remainder involved:
366 which is -8.
367 But integer division is supposed to discard the remainder,
369 (If you're having trouble seeing the way the shift worked,
372 The low-order 1 bit got shifted off to the right,
373 but because the high-order bit was 1,
374 a 1 got shifted in at the left.)
375 </p><hr>
376 <p>
377 Read sequentially:
382 </p>
383 <p>
387 </p>
388 </body>
389 </html>