49:
457:, also called POPCOUNT, which counts the number of set bits in a machine word, is also usually provided as a hardware operator. Simpler bit operations like bit set, reset, test and toggle are often provided as hardware operators, but are easily simulated if they aren't - for example (SET R0, 1; LSHFT R0, i; OR x, R0) sets bit i in operand x.
314:
To determine if a number is a power of two, conceptually we may repeatedly do integer divide by two until the number won't divide by 2 evenly; if the only factor left is 1, the original number was a power of 2. Using bit and logical operators, there is a simple expression which will return true (1)
214:
and operations to count ones and zeros, find high and low one or zero, set, reset and test bits, extract and insert fields, mask and zero fields, gather and scatter bits to and from specified bit positions or fields. Integer arithmetic operators can also effect bit-operations in conjunction with the
436:
Processors typically provide only a subset of the useful bit operators. Programming languages don't directly support most bit operations, so idioms must be used to code them. The 'C' programming language, for example provides only bit-wise AND(&), OR(|), XOR(^) and NOT(~). Fortran provides
297:
On most processors, the majority of bitwise operations are single cycle - substantially faster than division and multiplication and branches. While modern processors usually perform some arithmetic and logical operations just as fast as bitwise operations due to their longer
437:
AND(.and.), OR (.or.), XOR (.neqv.) and EQV(.eqv.). Algol provides syntactic bitfield extract and insert. When languages provide bit operations that don't directly map to hardware instructions, compilers must synthesize the operation from available operators.
482:
bitfield scatter/gather operations which distribute contiguous portions of a bitfield over a machine word, or gather disparate bitfields in the word into a contiguous portion of a bitfield (see recent Intel PEXT/PDEP operators). Used by cryptography and video
444:
used to find the high set bit of a machine word, though it may have different names on various architectures. There's no simple programming language idiom, so it must be provided by a compiler intrinsic or system library routine. Without that operator, it is
453:) to do any operations with regard to the high bit of a word, due to the asymmetric carry-propagate of arithmetic operations. Fortunately, most cpu architectures have provided that since the middle 1980s. An accompanying operation
422:) that counts the number of 1's or 0's in the operand might be available; an operand with exactly one '1' bit is a power of 2. However, such an instruction may have greater latency than the bitwise method above.
540:(etc.) can be set either on, off or inverted from on to off (or vice versa) in a single bitwise operation. More comprehensive applications of masking, when applied conditionally to operations, are termed
218:
Bit manipulation, in some cases, can obviate or reduce the need to loop over a data structure and can give manyfold speed-ups, as bit manipulations are processed in parallel.
241:
are often used interchangeably with bit manipulation, but sometimes exclusively refer to clever or non-obvious ways or uses of bit manipulation, or tedious or challenging
460:
Some of the more useful and complex bit operations that must be coded as idioms in the programming language and synthesized by compilers include:
260:
computer controls. As computer programming languages evolved, programmers adopted the term to mean any handling of data that involved bit-level
604:
541:
679:
657:
588:
690:
431:
132:
66:
717:
573:
669:
185:
113:
197:
85:
70:
593:
253:
20:
769:
537:
92:
764:
99:
59:
382:
The second half uses the fact that powers of two have one and only one bit set in their binary representation:
81:
291:
632:
On most Intel chips, it's BSR (bitscan reverse), though newer SoCs also have LZCNT (count leading zeros)
498:
Multiply by 9 for example, is copy operand, shift up by 3 (multiply by 8), and add to original operand.
303:
283:
306:
design choices, bitwise operations do commonly use less power because of the reduced use of resources.
210:: AND, OR, XOR, NOT, and possibly other operations analogous to the boolean operators; there are also
299:
189:
165:
713:
648:
242:
613:
737:
675:
653:
608:
518:
415:
273:
211:
207:
106:
512:
177:
173:
161:
157:
392:
If the number is neither zero nor a power of two, it will have '1' in more than one place:
694:
169:
687:
709:
450:
758:
583:
490:
Some arithmetic operations can be reduced to simpler operations and bit operations:
35:
563:
558:
279:
261:
203:
48:
31:
27:
672:
Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary
Decision Diagrams
193:
181:
568:
553:
522:
149:
294:(CPU), and is used to manipulate values for comparisons and calculations.
168:
tasks that require bit manipulation include low-level device control,
598:
533:
419:
731:
467:
clear from specified bit position down (leave upper part of word)
256:, where computer operators would make adjustments by tweaking or
529:
464:
clear from specified bit position up (leave lower part of word)
748:
577:
287:
153:
42:
389:
0...0 x-1 == 0...001...1 x & (x-1) == 0...000...0
290:. It is a fast, primitive action directly supported by the
674:(1st ed.). Addison–Wesley Professional. p. 272.
652:(2nd ed.). Addison–Wesley Professional. p. 512.
502:
reduce division by constant to sequence of shift-subtract
742:
494:
reduce multiply by constant to sequence of shift-add
601:— unit of data consisting of 4 bits, or half a byte
200:instead of bits that represent those abstractions.
73:. Unsourced material may be challenged and removed.
16:
Algorithmically modifying data below the word level
8:
278:A bitwise operation operates on one or more
206:that does bit manipulation makes use of the
470:mask from low bit down (clear lower word)
133:Learn how and when to remove this message
708:Anderson, Sean Eron, ed. (2009-11-26) .
473:mask from high bit up (clear lower word)
245:device control data manipulation tasks.
625:
734:with full explanations and source code
576:— bit manipulation extensions for the
440:An especially useful bit operation is
7:
71:adding citations to reliable sources
605:Predication (computer architecture)
418:code is used, then an instruction (
589:Bit specification (disambiguation)
14:
528:Using a mask, multiple bits in a
432:Bit Manipulation Instruction Sets
286:at the level of their individual
574:Bit manipulation instruction set
517:A mask is data that is used for
407:...001...1 x & (x-1) == 0...
47:
720:from the original on 2020-06-01
670:The Art of Computer Programming
188:. For most other tasks, modern
58:needs additional citations for
749:The Aggregate Magic Algorithms
607:where bit "masks" are used in
1:
594:Bit twiddler (disambiguation)
751:from University of Kentucky
426:Bit manipulation operations
310:Example of bit manipulation
786:
745:: x86_64 riddles and hacks
510:
429:
271:
25:
18:
667:Knuth, Donald E. (2009).
646:Warren, Henry S. (2013).
317:
254:early computing hardware
26:Not to be confused with
732:Bit Manipulation Tricks
697:available for download)
403:0...0 x-1 == 0...
292:central processing unit
738:Intel Intrinsics Guide
196:to work directly with
710:"Bit Twiddling Hacks"
300:instruction pipelines
190:programming languages
688:Draft of Fascicle 1a
521:, particularly in a
166:Computer programming
67:improve this article
19:For other uses, see
770:Computer arithmetic
714:Stanford University
442:count leading zeros
156:or other pieces of
693:2019-10-16 at the
614:Single-event upset
519:bitwise operations
451:Find first set#CLZ
385:x == 0...0
208:bitwise operations
82:"Bit manipulation"
765:Binary arithmetic
609:Vector processors
416:assembly language
395:x == 0...
274:Bitwise operation
268:Bitwise operation
215:other operators.
143:
142:
135:
117:
777:
728:
726:
725:
685:
663:
649:Hacker's Delight
633:
630:
580:instruction set.
513:Mask (computing)
486:matrix inversion
476:bitfield extract
410:
406:
402:
398:
388:
378:
375:
372:
369:
366:
363:
360:
357:
354:
351:
348:
345:
342:
339:
336:
333:
330:
327:
324:
321:
184:algorithms, and
178:data compression
146:Bit manipulation
138:
131:
127:
124:
118:
116:
75:
51:
43:
785:
784:
780:
779:
778:
776:
775:
774:
755:
754:
723:
721:
707:
704:
695:Wayback Machine
682:
666:
660:
645:
642:
640:Further reading
637:
636:
631:
627:
622:
550:
515:
509:
479:bitfield insert
449:expensive (see
434:
428:
412:
408:
404:
400:
396:
390:
386:
380:
379:
376:
373:
370:
367:
364:
361:
358:
355:
352:
349:
346:
343:
340:
337:
334:
331:
328:
325:
322:
319:
312:
284:binary numerals
276:
270:
224:
170:error detection
160:shorter than a
150:algorithmically
139:
128:
122:
119:
76:
74:
64:
52:
39:
24:
17:
12:
11:
5:
783:
781:
773:
772:
767:
757:
756:
753:
752:
746:
740:
735:
729:
703:
702:External links
700:
699:
698:
681:978-0321580504
680:
664:
659:978-0321842688
658:
641:
638:
635:
634:
624:
623:
621:
618:
617:
616:
611:
602:
596:
591:
586:
581:
571:
566:
561:
556:
549:
546:
511:Main article:
508:
505:
504:
503:
496:
495:
488:
487:
484:
480:
477:
474:
471:
468:
465:
427:
424:
394:
384:
318:
315:or false (0):
311:
308:
272:Main article:
269:
266:
239:bit gymnastics
223:
220:
148:is the act of
141:
140:
55:
53:
46:
15:
13:
10:
9:
6:
4:
3:
2:
782:
771:
768:
766:
763:
762:
760:
750:
747:
744:
743:xchg rax, rax
741:
739:
736:
733:
730:
719:
715:
711:
706:
705:
701:
696:
692:
689:
683:
677:
673:
671:
665:
661:
655:
651:
650:
644:
643:
639:
629:
626:
619:
615:
612:
610:
606:
603:
600:
597:
595:
592:
590:
587:
585:
584:BIT predicate
582:
579:
575:
572:
570:
567:
565:
562:
560:
557:
555:
552:
551:
547:
545:
543:
539:
535:
531:
526:
524:
520:
514:
506:
501:
500:
499:
493:
492:
491:
485:
481:
478:
475:
472:
469:
466:
463:
462:
461:
458:
456:
452:
448:
443:
438:
433:
425:
423:
421:
417:
393:
383:
316:
309:
307:
305:
304:architectural
301:
295:
293:
289:
285:
281:
275:
267:
265:
263:
259:
255:
251:
250:bit twiddling
246:
244:
240:
236:
232:
228:
227:Bit twiddling
221:
219:
216:
213:
209:
205:
201:
199:
195:
191:
187:
183:
179:
175:
171:
167:
163:
159:
155:
152:manipulating
151:
147:
137:
134:
126:
123:February 2020
115:
112:
108:
105:
101:
98:
94:
91:
87:
84: –
83:
79:
78:Find sources:
72:
68:
62:
61:
56:This article
54:
50:
45:
44:
41:
37:
33:
29:
22:
722:. Retrieved
668:
647:
628:
527:
516:
497:
489:
459:
454:
446:
441:
439:
435:
413:
391:
381:
323:isPowerOfTwo
313:
296:
280:bit patterns
277:
257:
249:
247:
238:
234:
231:bit fiddling
230:
226:
225:
217:
202:
198:abstractions
186:optimization
176:algorithms,
145:
144:
129:
120:
110:
103:
96:
89:
77:
65:Please help
60:verification
57:
40:
36:Byte grabber
21:Manipulation
564:Bit banging
559:Bit banding
542:predication
411:...000...0
262:computation
252:dates from
235:bit bashing
222:Terminology
204:Source code
32:Bit-banding
28:Bit-banging
759:Categories
724:2020-06-01
620:References
455:count ones
430:See also:
414:If inline
344:&&
302:and other
212:bit shifts
194:programmer
192:allow the
182:encryption
174:correction
93:newspapers
569:Bit field
554:Bit array
523:bit field
483:encoding.
258:twiddling
248:The term
243:low-level
718:Archived
691:Archived
548:See also
507:Masking
107:scholar
678:
656:
599:Nibble
534:nibble
420:popcnt
237:, and
109:
102:
95:
88:
80:
353:&
114:JSTOR
100:books
34:, or
676:ISBN
654:ISBN
538:word
530:Byte
447:very
399:...0
320:bool
288:bits
172:and
162:word
158:data
154:bits
86:news
578:x86
282:or
69:by
761::
716:.
712:.
544:.
536:,
532:,
525:.
377:);
371:==
368:))
347:((
335:!=
264:.
233:,
229:,
180:,
164:.
30:,
727:.
686:(
684:.
662:.
409:1
405:1
401:1
397:1
387:1
374:0
365:1
362:-
359:x
356:(
350:x
341:)
338:0
332:x
329:(
326:=
136:)
130:(
125:)
121:(
111:·
104:·
97:·
90:·
63:.
38:.
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
