140:
The count trailing zeros operation would return 3, while the count leading zeros operation returns 16. The count leading zeros operation depends on the word size: if this 32-bit word were truncated to a 16-bit word, count leading zeros would return zero. The find first set operation would return 4,
1947:
On platforms that provide hardware conversion of integers to floating point, the exponent field can be extracted and subtracted from a constant to compute the count of leading zeros. Corrections are needed to account for rounding errors. Floating point conversion can have substantial latency. This
1939:
clz5 (x) r = (x > 0xFFFF) << 4; x >>= r; q = (x > 0xFF ) << 3; x >>= q; r |= q; q = (x > 0xF ) << 2; x >>= q; r |= q; q = (x > 0x3 ) << 1; x >>= q; r |= q; r |= (x >> 1);
1540:
Most CPUs dating from the late 1980s onward have bit operators for ffs or equivalent, but a few modern ones like some of the ARM-Mx series do not. In lieu of hardware operators for ffs, clz and ctz, software can emulate them with shifts, integer arithmetic and bitwise operators. There are several
1901:
The fastest portable approaches to simulate clz are a combination of binary search and table lookup: an 8-bit table lookup (2=256 1-byte entries) can replace the bottom 3 branches in binary search. 64-bit operands require an additional branch. A larger width lookup can be used but the maximum
1932:
For processors with deep pipelines, like
Prescott and later Intel processors, it may be faster to replace branches by bitwise AND and OR operators (even though many more instructions are required) to avoid pipeline flushes for mispredicted branches (and these types of branches are inherently
1707:
implementation takes a logarithmic number of operations and branches, as in this 32-bit version: This algorithm can be assisted by a table as well, replacing the bottom three "if" statements with a 256 entry lookup table using the first non-zero byte encountered as an index.
155:
If the word is zero (no bits set), count leading zeros and count trailing zeros both return the number of bits in the word, while ffs returns zero. Both log base 2 and zero-based implementations of find first set generally return an undefined result for the zero word.
1227:
As demonstrated in the example above, the find first zero, count leading ones, and count trailing ones operations can be implemented by negating the input and using find first set, count leading zeros, and count trailing zeros. The reverse is also true.
1804:
The canonical algorithm examines one bit at a time starting from the MSB until a non-zero bit is found, as shown in this example. It executes in O(n) time where n is the bit-length of the operand, and is not a practical algorithm for general use.
1795:
The expression (x & -x) again isolates the least-significant 1 bit. There are then only 32 possible words, which the unsigned multiplication and shift hash to the correct position in the table. (This algorithm does not handle the zero input.)
1606:
Since ffs = ctz + 1 (POSIX) or ffs = ctz (other implementations), the applicable algorithms for ctz may be used, with a possible final step of adding 1 to the result, and returning 0 instead of the operand length for input of all zero bits.
1552:
Software emulations are usually deterministic. They return a defined result for all input values; in particular, the result for an input of all zero bits is usually 0 for ffs, and the bit length of the operand for the other operations.
1549:, search+table lookup, de Bruijn multiplication, floating point conversion/exponent extract, and bit operator (branchless) methods. There are tradeoffs between execution time and storage space as well as portability and efficiency.
722:
A number of compiler and library vendors supply compiler intrinsics or library functions to perform find first set and/or related operations, which are frequently implemented in terms of the hardware instructions above:
168:
to rapidly perform find first set and/or related operations, listed below. The most common operation is count leading zeros (clz), likely because all other operations can be implemented efficiently in terms of it (see
1909:
An algorithm similar to de Bruijn multiplication for CTZ works for CLZ, but rather than isolating the most-significant bit, it rounds up to the nearest integer of the form 2−1 using shifts and bitwise ORs:
1830:
An improvement on the previous looping approach examines eight bits at a time then uses a 256 (2) entry lookup table for the first non-zero byte. This approach, however, is still O(n) in execution time.
1556:
If one has a hardware clz or equivalent, ctz can be efficiently computed with bit operations, but the converse is not true: clz is not efficient to compute in the absence of a hardware operator.
2595:
2955:
1568:(round up to the nearest power of two) using shifts and bitwise ORs is not efficient to compute as in this 32-bit example and even more inefficient if we have a 64-bit or 128-bit operand:
1541:
approaches depending on architecture of the CPU and to a lesser extent, the programming language semantics and compiler code generation quality. The approaches may be loosely described as
109:
definition which starts indexing of bits at 1, herein labelled ffs, and the variant which starts indexing of bits at zero, which is equivalent to ctz and so will be called by that name.
70:), which counts the number of zero bits following the least significant one bit. The complementary operation that finds the index or position of the most significant set bit is
2803:
2902:
1902:
practical table size is limited by the size of L1 data cache on modern processors, which is 32 KB for many. Saving a branch is more than offset by the latency of an
54:, designates the index or position of the least significant bit set to one in the word counting from the least significant bit position. A nearly equivalent operation is
2210:
spends many cycles removing trailing zeros; this can be replaced by a count trailing zeros (ctz) followed by a shift. A similar loop appears in computations of the
3007:
152:
The count trailing ones operation would return 3, the count leading ones operation would return 16, and the find first zero operation ffz would return 4.
3786:
1171:
If bits are labeled starting at 1 (which is the convention used in this article), then count trailing zeros and find first set operations are related by
3417:
1913:
table = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31}
521:
3832:
3747:
3606:
3348:
3314:
3689:
2225:. In this context, find first set (ffs) is useful in implementing the "pop" or "pull highest priority element" operation efficiently. The
3751:
2149:, where ">>" is unsigned right shift. It can be used to perform more sophisticated bit operations like finding the first string of
3112:
2873:
2666:
2169:
technique that encodes an integer as the number of leading zero bytes together with the nonzero bytes. It can also efficiently generate
3537:
2790:
3184:
105:), which counts the number of zero bits preceding the most significant one bit. There are two common variants of find first set, the
2269:
952:
948:
393:
367:
363:
116:
provide one or more of these as hardware operators; software emulation is usually provided for any that aren't available, either as
2585:
2506:
3851:
3729:
3394:
2770:
2561:
3505:
3140:
2833:
2612:
2174:
2963:
2935:
981:
235:
203:
2145:
Count leading zeros (clz) can be used to compute the 32-bit predicate "x = y" (zero if true, one if false) via the identity
1532:) is encountered. A tree data structure that recursively uses bitmaps to track which words are nonzero can accelerate this.
2248:) is moved the minimum possible distance to the right (circling back around to the left as needed). It can also generate a
2200:
2799:
1767:
3907:
113:
51:
2135:
2134:
has its most significant bit in a known position (such as the highest position). This can in turn be used to implement
2442:
3659:
2414:
3902:
1770:
that eliminates all branches. This algorithm assumes that the result of the multiplication is truncated to 32 bit.
3889:: A detailed explanation of a number of implementation methods for ffs (called LS1B) and log base 2 (called MS1B).
2170:
1085:
3773:
2717:"Chapter 3.3.13 Fixed-Point Logical Instructions - Chapter 3.3.13.1 64-bit Fixed-Point Logical Instructions".
1693:
3825:
3580:
3341:
850:
3782:
3667:
3390:
2557:
2536:
3864:
3564:
2742:
2697:
1508:
in a straightforward manner by starting at one end and proceeding until a word that is not all-zero (for
3868:
2373:
2983:
3441:
2718:
992:
3490:
3409:
2207:
1648:) time and operations, and is impractical in practice due to a large number of conditional branches.
3672:
3233:
2389:
3847:
3815:
3331:
2927:
1615:
The canonical algorithm is a loop counting zeros starting at the LSB until a 1-bit is encountered:
1276:
3056:
3695:
3382:
3084:
3028:
2453:
2211:
1763:
1037:
117:
3881:
2527:
2158:
2587:
Intel
Itanium Architecture Software Developer's Manual. Volume 3: Intel Itanium Instruction Set
3828:
3733:
3685:
3602:
3344:
3310:
3306:
3295:
2652:
2618:
2449:
437:
2679:
3677:
3530:
2776:
2344:
2166:
1700:. But as a linear lookup, this approach is still O(n) in the number of bits in the operand.
231:
199:
121:
75:
2551:"AMD64 Architecture Programmer's Manual, Volume 3: General-Purpose and System Instructions"
3598:
1749:
If the hardware has a clz operator, the most efficient approach to computing ctz is thus:
165:
2374:
Find the log base 2 of an integer with the MSB N set in O(N) operations (the obvious way)
3207:
2529:
AMD64 Architecture
Programmer's Manual Volume 3: General Purpose and System Instructions
2309:
Using bit operations on other than an unsigned machine word may yield undefined results.
1187:, then count trailing zeros and find first set are exactly equivalent operations. Given
3821:
3565:
Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup
3368:
3337:
2285:
2237:
2222:
2180:
The log base 2 can be used to anticipate whether a multiplication will overflow, since
2139:
1697:
1376:
657:
476:
3843:
3386:
2157:
is an effective initial guess for computing the square root of a 32-bit integer using
1306:
On platforms with an efficient count leading zeros operation such as ARM and PowerPC,
3896:
3498:
3494:
3302:
2846:
2646:
2622:
2422:
2343:
find the index of the most significant zero bit, which is an inverted version of the
2290:
2275:
1704:
1546:
1542:
963:
926:
895:
47:
144:
Similarly, given the following 32-bit word, the bitwise negation of the above word:
17:
3699:
2480:
2280:
2226:
2203:, which can find the period of a function of finite range using limited resources.
209:
3664:
Proceedings of the Sixth
International Workshop on Data Management on New Hardware
2415:"ARM Instruction Reference > ARM general data processing instructions > CLZ"
3725:
2995:
Clang supports a number of builtin library functions with the same syntax as GCC
2881:
319:
3259:
2334:, which counts the number of one bits following the least significant zero bit.
2199:
Count leading zeros and count trailing zeros can be used together to implement
3743:
2340:, which counts the number of one bits preceding the most significant zero bit;
3287:
2122:
The count leading zeros (clz) operation can be used to efficiently implement
3681:
3120:
3092:
3064:
3036:
2550:
2249:
2218:
1505:
551:
529:
280:
141:
indicating the 4th position from the right. The truncated log base 2 is 15.
3886:
1504:
Find first set and related operations can be extended to arbitrarily large
2648:
MIPS Architecture For
Programmers. Volume II-A: The MIPS64 Instruction Set
2614:
MIPS Architecture For
Programmers. Volume II-A: The MIPS32 Instruction Set
2236:
The count trailing zeros operation gives a simple optimal solution to the
2675:
2668:
M68000 Family
Programmer's Reference Manual (Includes CPU32 Instructions)
1903:
1388:
31:
2845:. March 2015. pp. 7-219–22-10. SA22-7832-10. Archived from
1119:
822:
785:
525:
415:
3164:
3738:
3595:
ARM system developer's guide designing and optimizing system software
3193:
2489:
2318:
These four operations also have (much less common) negated versions:
980:
Relies on hardware support for the clz instruction introduced in the
754:
573:
499:
3742:(retyped & converted ed.). Cambridge, Massachusetts, USA:
947:
Relies on hardware support for the lzcnt instruction introduced in
3581:
Find the integer log base 2 of an integer with a 64-bit IEEE float
3170:
3144:
2591:
2512:
1380:
855:
774:
749:
613:
258:
106:
3863:(NB. Lists several efficient public domain C implementations for
3662:(June 2010). "Fast integer compression using SIMD instructions".
1183:(except when the input is zero). If bits are labeled starting at
2678:. 1992. pp. 4-43–4-45. M68000PRM/AD. Archived from
2328:), which identifies the index of the least significant zero bit;
1057:
1020:
714:
On some Alpha platforms CTLZ and CTTZ are emulated in software.
2696:
Frey, Brad. "Chapter 3.3.11 Fixed-Point
Logical Instructions".
1849:(x & t) = 0 t ← t >> 8 r ← r + 8
1823:(x & t) = 0 t ← t >> 1 r ← r + 1
1633:(x & t) = 0 t ← t << 1 r ← r + 1
2842:
2724:
2703:
887:
GCC documentation considers result undefined clz and ctz on 0.
635:
389:
359:
3636:. Chapter 6-2: Find First String of 1-Bits of a Given Length.
2155:
clz(x − y)1 << (16 − clz(x − 1)/2)
1890:(x & 0xC0000000) = 0: n ← n + 2, x ← x << 2
1886:(x & 0xF0000000) = 0: n ← n + 4, x ← x << 4
1882:(x & 0xFF000000) = 0: n ← n + 8, x ← x << 8
1878:(x & 0xFFFF0000) = 0: n ← n + 16, x ← x << 16
1738:(x & 0x00000003) = 0: n ← n + 2, x ← x >> 2
1734:(x & 0x0000000F) = 0: n ← n + 4, x ← x >> 4
1730:(x & 0x000000FF) = 0: n ← n + 8, x ← x >> 8
1726:(x & 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16
3504:. MIT Laboratory for Computer Science, Cambridge, MA, USA.
3499:"Using de Bruijn Sequences to Index a 1 in a Computer Word"
1948:
method is highly non-portable and not usually recommended.
777:. POSIX does not supply the complementary log base 2 / clz.
3235:
N4861 Working Draft, Standard for
Programming Language C++
2508:
Intel 64 and IA-32 Architectures
Software Developer Manual
3301:(Version 8 ed.). Englewood Cliffs, New Jersey, USA:
1080:
Operand width, if 2nd argument is 0; undefined otherwise
3593:
Sloss, Andrew N.; Symes, Dominic; Wright, Chris (2004).
3010:. LLVM Team, University of Illinois at Urbana-Champaign
2984:"Clang Language Extensions - chapter Builtin Functions"
2240:
problem: the disks are numbered from zero, and at move
1586:is implementation defined (not in ) x ← x - 1
2736:
2734:
2539:(AMD). 2011. pp. 204–205. Publication No. 24594.
1685:
r + table x ← x >> n r ← r + n
27:
Family of related bitwise operations on machine words
3117:
Visual Studio 2012: Visual C++: Compiler Intrinsics
3089:
Visual Studio 2008: Visual C++: Compiler Intrinsics
3061:
Visual Studio 2008: Visual C++: Compiler Intrinsics
3033:
Visual Studio 2008: Visual C++: Compiler Intrinsics
2501:
2499:
2475:
2473:
3473:
3471:
3469:
3456:
3454:
3452:
3450:
3294:
3208:"'llvm.ctlz.*' Intrinsic, 'llvm.cttz.*' Intrinsic"
2868:
2866:
2743:"RISC-V "B" Bit Manipulation Extension for RISC-V"
3281:
3279:
3166:Intel C++ Compiler for Linux Intrinsics Reference
2384:
2382:
2252:by taking an arbitrary word and flipping bit ctz(
3371:. 2001. pp. 8–24. Part Number 82-000410-14.
2142:conversion in software, and other applications.
1856:Binary search can reduce execution time to O(log
2641:
2639:
2607:
2605:
2560:(AMD). September 2019 . Publication No. 24594.
814:fls("find last set") computes (log base 2) + 1.
1845:w t ← 0xff << (w - 8) r ← 0
3775:Understanding the Linux 2.6.8.1 CPU Scheduler
1925:{1, 2, 4, 8, 16}: x ← x | (x >> y)
1594:{1, 2, 4, 8, 16}: x ← x | (x >> y)
1299:bit, so that the most- and least-significant
170:
86:
8:
2827:
2825:
2823:
2556:. AMD64 Technology (Version 3.28 ed.).
2272:(BMI) for Intel and AMD x86-based processors
1651:A lookup table can eliminate most branches:
918:Separate return value to indicate zero input
2832:"Chapter 22. Vector Integer Instructions".
1819:w t ← 1 << (w - 1) r ← 0
3288:"A.41: Population Count. Programming Note"
2928:"Other built-in functions provided by GCC"
2835:IBM z/Architecture Principles of Operation
3671:
1894:(x & 0x80000000) = 0: n ← n + 1
1742:(x & 0x00000001) = 0: n ← n + 1
3297:The SPARC architecture manual: version 8
2621:. 2011. pp. 101–102. Archived from
1692:is fixed (typically 8) and represents a
725:
614:SPARC Oracle Architecture 2011 and later
175:
3442:Round up to the next highest power of 2
2932:Using the GNU Compiler Collection (GCC)
2362:
2302:
148:1111 1111 1111 1111 0111 1111 1111 0111
136:0000 0000 0000 0000 1000 0000 0000 1000
3624:. Chapter 2-11: Comparison Predicates.
3597:(1 ed.). San Francisco, CA, USA:
1036:Compiles to fewer instructions on the
3748:Massachusetts Institute of Technology
3658:Schlegel, Benjamin; Gemulla, Rainer;
3480:. Chapter 5-4: Counting Trailing 0's.
3260:"Standard library header <bit>"
2452:. 2011. 32000D–04/201. Archived from
1784:31: table ← i // table initialized
1494:) can be computed with a left-shift (
1379:(population count) operation such as
1295:clears all but the least-significant
7:
3648:. Chapter 11-1: Integer Square Root.
3463:. Chapter 5-3: Counting Leading 0's.
3057:"_BitScanReverse, _BitScanReverse64"
3029:"_BitScanForward, _BitScanForward64"
2655:. 2011. pp. 105, 107, 122, 123.
2492:. 2002. pp. 4-32, 4-34.
2229:real-time scheduler internally uses
74:, so called because it computes the
3715:. Chapter 2-12: Overflow Detection.
2482:Alpha Architecture Reference Manual
2419:ARM Developer Suite Assembler Guide
3744:Artificial Intelligence Laboratory
3497:; Randall, Keith H. (1998-07-07).
3365:Blackfin Instruction Set Reference
3286:SPARC International, Inc. (1992).
3214:. The LLVM Compiler Infrastructure
1231:On platforms with an efficient log
25:
2792:VAX Architecture Reference Manual
2270:Bit Manipulation Instruction Sets
2201:Gosper's loop-detection algorithm
1762:An algorithm for 32-bit ctz uses
132:Given the following 32-bit word:
3531:"Computing Trailing Zeros HOWTO"
3397:from the original on 2019-10-31.
3387:"The Aggregate Magic Algorithms"
2907:FreeBSD Library Functions Manual
2598:from the original on 2019-06-26.
2161:. CLZ can efficiently implement
1681:(x & (2-1)) ≠ 0
1333:Conversely, on machines without
3887:Chess Programming Wiki: BitScan
3854:from the original on 2020-01-08
3814:Warren, Jr., Henry S. (2013) .
3792:from the original on 2017-05-19
3754:from the original on 2019-10-08
3543:from the original on 2016-08-01
3511:from the original on 2020-01-09
3420:from the original on 2020-01-09
3330:Warren, Jr., Henry S. (2013) .
3085:"__lzcnt16, __lzcnt, __lzcnt64"
2809:from the original on 2019-09-29
2567:from the original on 2019-09-30
1375:On platforms with an efficient
410:Operand width; sets carry flag
384:Operand width; sets carry flag
3408:Isenberg, Gerd (2019-11-03) .
3212:LLVM Language Reference Manual
2964:Free Software Foundation, Inc.
2936:Free Software Foundation, Inc.
2772:Oracle SPARC Architecture 2011
2173:integers by taking the clz of
2126:, which encodes an integer as
1460:denotes bitwise exclusive-OR,
652:Operand width; sets zero flag
1:
3842:Anderson, Sean Eron (2005) .
3750:(MIT). AI Memo 239 Item 132.
3576:
3560:
3529:Busch, Philip (2009-03-01) .
3437:
3241:. ISO/IEC. pp. 1150–1153
3232:Smith, Richard (2020-04-01).
3186:NVIDIA CUDA Programming Guide
2802:(DEC). 1987. pp. 70–71.
2800:Digital Equipment Corporation
2741:Wolf, Clifford (2019-03-22).
2515:. pp. 3-92–3-97.
2443:"AVR32 Architecture Document"
2369:
1768:minimal perfect hash function
1755:ctz4 (x) x &= -x
1696:. The loop may also be fully
982:ARMv5T architecture and later
204:ARMv5T architecture and later
114:instruction set architectures
3414:Chess Programming Wiki (CPW)
2025:// LE is 1 for little-endian
1200:is easily computed from the
1122:standard library, in header
1111:Haskell programming language
699:Vector Count Trailing Zeroes
3712:
3645:
3633:
3621:
3477:
3460:
2396:. The Linux Kernel Archives
2221:can be used to implement a
1471:The inverse problem (given
682:Vector Count Leading Zeroes
494:Field offset + field width
485:Find First One in Bit Field
445:Count Leading Zeros in Word
164:Many architectures include
3924:
2878:Mac OS X Developer Library
2651:(Revision 3.02 ed.).
2617:(Revision 3.02 ed.).
1629:w t ← 1 r ← 0
1468:denotes bitwise negation.
1451:clz = 32 − popcount(2 − 1)
1235:operation such as M68000,
462:Count Leading Ones in Word
354:Undefined; sets zero flag
337:Undefined; sets zero flag
2702:(Version 2.02 ed.).
2699:PowerPC Architecture Book
2394:Linux Programmer's Manual
2171:exponentially distributed
1035:
1032:
1029:
1018:
656:
572:
436:
318:
279:
3772:Aas, Josh (2005-02-17).
3367:(Preliminary ed.).
3192:(Version 3.0 ed.).
3141:"Intel Intrinsics Guide"
2752:(Draft) (v0.37 ed.)
1950:
1640:This algorithm executes
1352:, albeit inefficiently:
1269:denotes bitwise AND and
1167:Properties and relations
718:Tool and library support
171:Properties and relations
64:number of trailing zeros
50:that, given an unsigned
3826:Pearson Education, Inc.
3730:Baker, Henry Givens Jr.
3682:10.1145/1869389.1869394
3342:Pearson Education, Inc.
2674:(revision 1 ed.).
2594:. 2010. pp. 3:38.
2448:(CORP072610 ed.).
2153:1 bits. The expression
2136:Newton–Raphson division
1464:denotes bitwise OR and
552:Power ISA 3.0 and later
99:number of leading zeros
3882:Intel Intrinsics Guide
3783:Silicon Graphics, Inc.
3391:University of Kentucky
3008:"Source code of Clang"
2720:Power ISA Version 3.0B
2558:Advanced Micro Devices
2537:Advanced Micro Devices
2231:sched_find_first_bit()
2130: × 2, where
1520:) or not all-one (for
1348:can be computed using
1141:countr_zero countr_one
1137:countl_zero countl_one
1077:LLVM assembly language
507:Jump if Find First One
3844:"Bit Twiddling Hacks"
3491:Leiserson, Charles E.
2956:"GCC 3.4.0 ChangeLog"
2909:. The FreeBSD Project
2841:(Eleventh ed.).
2147:clz(x − y) >> 5
2138:, perform integer to
3865:count trailing zeros
3601:. pp. 212–213.
2517:Order number 325383.
2208:binary GCD algorithm
1310:can be computed by:
1239:can be computed by:
1107:FiniteBits b => b
1088:7.10 (base 4.8), in
744:On application to 0
618:lzcnt (synonym: lzd)
599:Count Trailing Zeros
559:Count Trailing Zeros
401:Count Trailing Zeros
305:Count Trailing Zeros
236:ARMv8-A architecture
210:Cortex-M0/M0+/M1/M23
194:On application to 0
56:count trailing zeros
18:Count trailing zeros
3908:Computer arithmetic
3848:Stanford University
3785:(SGI). p. 19.
3383:Dietz, Henry Gordon
3196:. 2010. p. 92.
3173:. 2006. p. 21.
2332:count trailing ones
1764:de Bruijn sequences
1694:time–space tradeoff
1371:for the zero input)
1193:bits per word, the
1006:Compiler intrinsics
910:Compiler intrinsics
882:unsigned long long,
582:Count Leading Zeros
537:Count Leading Zeros
534:cntlz/cntlzw/cntlzd
423:Count Leading Zeros
375:Count Leading Zeros
288:Count Leading Zeros
266:Count Leading Zeros
244:Count Leading Zeros
217:Count Leading Zeros
118:compiler intrinsics
91:count leading zeros
3666:. pp. 34–40.
3410:"BitScanProtected"
2727:. pp. 95, 98.
2338:count leading ones
2244:, disk number ctz(
2233:for this purpose.
2212:hailstone sequence
2058:4503599627370496.0
1536:Software emulation
1363:(which depends on
1303:bit are the same.
1204:and vice versa by
1156:unsigned long long
1129:bit_ceil bit_floor
1099:countTrailingZeros
1074:8, 16, 32, 64, 256
1038:GeForce 400 series
993:Intel C++ Compiler
974:Compiler intrinsic
937:Compiler intrinsic
875:Built-in functions
658:IBM z/Architecture
621:Leading Zero Count
3903:Binary arithmetic
3834:978-0-321-84268-8
3608:978-1-55860-874-0
3350:978-0-321-84268-8
3316:978-0-13-825001-0
2653:MIPS Technologies
2619:MIPS Technologies
2450:Atmel Corporation
1874:32 n ← 0
1759:w - (clz(x) + 1)
1722:32 n ← 0
1285:. The expression
1164:
1163:
1095:countLeadingZeros
1002:_bit_scan_reverse
998:_bit_scan_forward
752:.1 compliant libc
712:
711:
665:Find Leftmost One
16:(Redirected from
3915:
3862:
3860:
3859:
3838:
3837:. 0-321-84268-5.
3817:Hacker's Delight
3801:
3800:
3798:
3797:
3791:
3780:
3769:
3763:
3762:
3760:
3759:
3722:
3716:
3710:
3704:
3703:
3691:978-1-45030189-3
3675:
3660:Lehner, Wolfgang
3655:
3649:
3643:
3637:
3631:
3625:
3619:
3613:
3612:
3590:
3584:
3574:
3568:
3558:
3552:
3551:
3549:
3548:
3542:
3535:
3526:
3520:
3519:
3517:
3516:
3510:
3503:
3487:
3481:
3475:
3464:
3458:
3445:
3435:
3429:
3428:
3426:
3425:
3405:
3399:
3398:
3379:
3373:
3372:
3361:
3355:
3354:
3353:. 0-321-84268-5.
3333:Hacker's Delight
3327:
3321:
3320:
3300:
3292:
3283:
3274:
3273:
3271:
3270:
3264:cppreference.com
3256:
3250:
3249:
3247:
3246:
3240:
3229:
3223:
3222:
3220:
3219:
3204:
3198:
3197:
3191:
3181:
3175:
3174:
3161:
3155:
3154:
3152:
3151:
3137:
3131:
3130:
3128:
3127:
3113:"ARM intrinsics"
3109:
3103:
3102:
3100:
3099:
3081:
3075:
3074:
3072:
3071:
3053:
3047:
3046:
3044:
3043:
3025:
3019:
3018:
3016:
3015:
3004:
2998:
2997:
2992:
2991:
2986:. The Clang Team
2980:
2974:
2973:
2971:
2970:
2952:
2946:
2945:
2943:
2942:
2924:
2918:
2917:
2915:
2914:
2899:
2893:
2892:
2890:
2889:
2870:
2861:
2860:
2858:
2857:
2851:
2840:
2829:
2818:
2817:
2815:
2814:
2808:
2797:
2787:
2781:
2780:
2767:
2761:
2760:
2758:
2757:
2747:
2738:
2729:
2728:
2714:
2708:
2707:
2693:
2687:
2686:
2684:
2673:
2663:
2657:
2656:
2643:
2634:
2633:
2631:
2630:
2609:
2600:
2599:
2582:
2576:
2575:
2573:
2572:
2566:
2555:
2547:
2541:
2540:
2534:
2524:
2518:
2516:
2511:. Vol. 2A.
2503:
2494:
2493:
2487:
2477:
2468:
2467:
2465:
2464:
2458:
2447:
2439:
2433:
2432:
2430:
2429:
2411:
2405:
2404:
2402:
2401:
2386:
2377:
2367:
2350:
2345:binary logarithm
2316:
2310:
2307:
2232:
2195:
2175:uniformly random
2167:data compression
2163:null suppression
2156:
2148:
2113:
2110:
2107:
2104:
2101:
2098:
2095:
2092:
2089:
2086:
2083:
2080:
2077:
2074:
2071:
2068:
2065:
2062:
2059:
2056:
2053:
2050:
2047:
2044:
2041:
2038:
2035:
2032:
2029:
2026:
2023:
2020:
2017:
2014:
2011:
2008:
2005:
2002:
1999:
1996:
1993:
1990:
1987:
1984:
1981:
1978:
1975:
1972:
1969:
1966:
1963:
1960:
1957:
1954:
1933:unpredictable):
1674:w r ← 0
1567:
1531:
1527:
1523:
1519:
1515:
1511:
1500:
1493:
1482:
1476:
1467:
1463:
1459:
1452:
1447:
1429:
1413:
1394:
1386:
1370:
1366:
1362:
1351:
1347:
1343:
1339:
1328:
1309:
1302:
1298:
1294:
1284:
1277:two's complement
1274:
1268:
1261:
1238:
1223:
1203:
1199:
1192:
1186:
1182:
1145:Library function
1142:
1138:
1134:
1130:
1125:
1108:
1103:Library function
1100:
1096:
1091:
1068:
1064:
1049:
1027:
1003:
999:
971:
944:unsigned __int64
934:
915:unsigned __int64
907:
903:
871:
867:
863:
837:Library function
834:
830:
806:Library function
803:
799:
795:
767:Library function
764:
726:
576:("B" Extension)
516:0; no operation
345:Bit Scan Reverse
328:Bit Scan Forward
176:
160:Hardware support
122:system libraries
112:Most modern CPU
84:
76:binary logarithm
21:
3923:
3922:
3918:
3917:
3916:
3914:
3913:
3912:
3893:
3892:
3878:
3857:
3855:
3841:
3835:
3813:
3810:
3808:Further reading
3805:
3804:
3795:
3793:
3789:
3778:
3771:
3770:
3766:
3757:
3755:
3734:"Loop detector"
3728:(April 1995) .
3724:
3723:
3719:
3711:
3707:
3692:
3673:10.1.1.230.6379
3657:
3656:
3652:
3644:
3640:
3632:
3628:
3620:
3616:
3609:
3599:Morgan Kaufmann
3592:
3591:
3587:
3575:
3571:
3559:
3555:
3546:
3544:
3540:
3533:
3528:
3527:
3523:
3514:
3512:
3508:
3501:
3489:
3488:
3484:
3476:
3467:
3459:
3448:
3436:
3432:
3423:
3421:
3407:
3406:
3402:
3381:
3380:
3376:
3363:
3362:
3358:
3351:
3329:
3328:
3324:
3317:
3290:
3285:
3284:
3277:
3268:
3266:
3258:
3257:
3253:
3244:
3242:
3238:
3231:
3230:
3226:
3217:
3215:
3206:
3205:
3201:
3189:
3183:
3182:
3178:
3163:
3162:
3158:
3149:
3147:
3139:
3138:
3134:
3125:
3123:
3111:
3110:
3106:
3097:
3095:
3083:
3082:
3078:
3069:
3067:
3055:
3054:
3050:
3041:
3039:
3027:
3026:
3022:
3013:
3011:
3006:
3005:
3001:
2989:
2987:
2982:
2981:
2977:
2968:
2966:
2954:
2953:
2949:
2940:
2938:
2926:
2925:
2921:
2912:
2910:
2901:
2900:
2896:
2887:
2885:
2872:
2871:
2864:
2855:
2853:
2849:
2838:
2831:
2830:
2821:
2812:
2810:
2806:
2795:
2789:
2788:
2784:
2769:
2768:
2764:
2755:
2753:
2745:
2740:
2739:
2732:
2716:
2715:
2711:
2695:
2694:
2690:
2682:
2671:
2665:
2664:
2660:
2645:
2644:
2637:
2628:
2626:
2611:
2610:
2603:
2590:. Vol. 3.
2584:
2583:
2579:
2570:
2568:
2564:
2553:
2549:
2548:
2544:
2535:. Vol. 3.
2532:
2526:
2525:
2521:
2505:
2504:
2497:
2485:
2479:
2478:
2471:
2462:
2460:
2456:
2445:
2441:
2440:
2436:
2427:
2425:
2413:
2412:
2408:
2399:
2397:
2388:
2387:
2380:
2368:
2364:
2359:
2354:
2353:
2322:find first zero
2317:
2313:
2308:
2304:
2299:
2266:
2230:
2193:
2189:
2185:
2181:
2159:Newton's method
2154:
2146:
2120:
2115:
2114:
2111:
2108:
2105:
2102:
2099:
2096:
2093:
2090:
2087:
2084:
2081:
2078:
2075:
2072:
2069:
2066:
2063:
2060:
2057:
2054:
2051:
2048:
2045:
2042:
2039:
2036:
2033:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1994:
1991:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1955:
1952:
1945:
1930:
1899:
1859:
1854:
1828:
1802:
1793:
1766:to construct a
1760:
1747:
1686:
1654:table = ctz(i)
1638:
1613:
1604:
1599:
1565:
1562:
1538:
1529:
1525:
1521:
1517:
1513:
1509:
1495:
1484:
1478:
1472:
1465:
1461:
1457:
1450:
1433:
1420:) = popcount(~(
1415:
1399:
1392:
1384:
1368:
1364:
1356:
1349:
1345:
1341:
1338:
1334:
1314:
1307:
1300:
1296:
1286:
1280:
1270:
1266:
1251:
1243:
1236:
1234:
1209:
1205:
1201:
1198:
1194:
1188:
1184:
1172:
1169:
1155:
1153:
1151:
1150:unsigned short,
1149:
1140:
1139:
1136:
1135:
1132:
1131:
1128:
1123:
1106:
1098:
1097:
1094:
1089:
1066:
1065:
1062:
1047:
1025:
1001:
1000:
997:
969:
943:
941:
940:unsigned short,
932:
914:
906:_BitScanReverse
905:
904:
902:_BitScanForward
901:
883:
881:
879:
872:
869:
868:
865:
864:
861:
854:
832:
831:
828:
810:
801:
800:
797:
796:
793:
789:
762:
758:
753:
720:
207:
162:
130:
87:closely related
82:
78:
28:
23:
22:
15:
12:
11:
5:
3921:
3919:
3911:
3910:
3905:
3895:
3894:
3891:
3890:
3884:
3877:
3876:External links
3874:
3873:
3872:
3839:
3833:
3822:Addison Wesley
3820:(2 ed.).
3809:
3806:
3803:
3802:
3764:
3717:
3705:
3690:
3650:
3638:
3626:
3614:
3607:
3585:
3569:
3553:
3521:
3495:Prokop, Harald
3482:
3465:
3446:
3430:
3400:
3374:
3369:Analog Devices
3356:
3349:
3338:Addison Wesley
3336:(2 ed.).
3322:
3315:
3275:
3251:
3224:
3199:
3176:
3156:
3132:
3104:
3076:
3048:
3020:
2999:
2975:
2947:
2919:
2894:
2862:
2819:
2782:
2762:
2730:
2709:
2688:
2685:on 2019-12-08.
2658:
2635:
2601:
2577:
2542:
2519:
2495:
2469:
2434:
2406:
2378:
2361:
2360:
2358:
2355:
2352:
2351:
2349:
2348:
2341:
2335:
2329:
2311:
2301:
2300:
2298:
2295:
2294:
2293:
2288:
2286:Trailing digit
2283:
2278:
2273:
2265:
2262:
2238:Tower of Hanoi
2223:priority queue
2191:
2187:
2183:
2140:floating point
2119:
2116:
1951:
1935:
1912:
1862:
1857:
1833:
1807:
1801:
1798:
1772:
1751:
1710:
1688:The parameter
1653:
1617:
1612:
1609:
1603:
1600:
1570:
1561:
1558:
1537:
1534:
1454:
1453:
1448:
1431:
1404:) = popcount((
1377:Hamming weight
1373:
1372:
1336:
1331:
1330:
1263:
1262:
1249:
1232:
1207:
1196:
1168:
1165:
1162:
1161:
1159:
1157:
1154:unsigned long,
1148:unsigned char,
1146:
1143:
1126:
1116:
1115:
1114:Operand width
1112:
1109:
1104:
1101:
1092:
1082:
1081:
1078:
1075:
1072:
1069:
1060:
1054:
1053:
1050:
1044:
1043:
1040:
1034:
1033:32-bit, 64-bit
1031:
1028:
1023:
1016:
1015:
1012:
1010:
1007:
1004:
995:
989:
988:
985:
978:
975:
972:
967:
960:
959:
958:Operand width
956:
945:
938:
935:
930:
923:
922:
919:
916:
913:unsigned long,
911:
908:
899:
892:
891:
888:
885:
880:unsigned long,
876:
873:
859:
847:
846:
843:
841:
838:
835:
826:
819:
818:
815:
812:
807:
804:
791:
790:OS X 10.4 libc
782:
781:
778:
771:
768:
765:
760:
759:OS X 10.3 libc
746:
745:
742:
739:
736:
733:
730:
719:
716:
710:
709:
708:Operand width
706:
703:
700:
697:
693:
692:
691:Operand width
689:
686:
683:
680:
676:
675:
672:
669:
666:
663:
660:
654:
653:
650:
647:
644:
643:Find First Set
641:
638:
632:
631:
628:
625:
622:
619:
616:
610:
609:
608:Operand width
606:
603:
600:
597:
593:
592:
591:Operand width
589:
586:
583:
580:
577:
570:
569:
568:Operand width
566:
563:
560:
557:
554:
548:
547:
546:Operand width
544:
541:
538:
535:
532:
518:
517:
514:
511:
508:
505:
502:
496:
495:
492:
489:
486:
483:
480:
477:Motorola 68020
473:
472:
471:Operand width
469:
466:
463:
460:
456:
455:
454:Operand width
452:
449:
446:
443:
440:
434:
433:
430:
427:
424:
421:
418:
412:
411:
408:
405:
402:
399:
396:
386:
385:
382:
379:
376:
373:
370:
356:
355:
352:
349:
346:
343:
339:
338:
335:
332:
329:
326:
323:
316:
315:
312:
309:
306:
303:
299:
298:
295:
292:
289:
286:
283:
277:
276:
273:
270:
267:
264:
261:
255:
254:
253:Operand width
251:
248:
245:
242:
239:
228:
227:
224:
221:
218:
215:
212:
196:
195:
192:
189:
188:Operand widths
186:
183:
180:
161:
158:
150:
149:
138:
137:
129:
126:
80:
44:find first one
36:find first set
34:and hardware,
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3920:
3909:
3906:
3904:
3901:
3900:
3898:
3888:
3885:
3883:
3880:
3879:
3875:
3870:
3866:
3853:
3849:
3845:
3840:
3836:
3830:
3827:
3823:
3819:
3818:
3812:
3811:
3807:
3788:
3784:
3777:
3776:
3768:
3765:
3753:
3749:
3745:
3741:
3740:
3735:
3731:
3727:
3721:
3718:
3714:
3709:
3706:
3701:
3697:
3693:
3687:
3683:
3679:
3674:
3669:
3665:
3661:
3654:
3651:
3647:
3642:
3639:
3635:
3630:
3627:
3623:
3618:
3615:
3610:
3604:
3600:
3596:
3589:
3586:
3582:
3578:
3573:
3570:
3566:
3562:
3557:
3554:
3539:
3532:
3525:
3522:
3507:
3500:
3496:
3492:
3486:
3483:
3479:
3474:
3472:
3470:
3466:
3462:
3457:
3455:
3453:
3451:
3447:
3443:
3439:
3434:
3431:
3419:
3415:
3411:
3404:
3401:
3396:
3392:
3388:
3384:
3378:
3375:
3370:
3366:
3360:
3357:
3352:
3346:
3343:
3339:
3335:
3334:
3326:
3323:
3318:
3312:
3308:
3304:
3303:Prentice Hall
3299:
3298:
3289:
3282:
3280:
3276:
3265:
3261:
3255:
3252:
3237:
3236:
3228:
3225:
3213:
3209:
3203:
3200:
3195:
3188:
3187:
3180:
3177:
3172:
3168:
3167:
3160:
3157:
3146:
3142:
3136:
3133:
3122:
3118:
3114:
3108:
3105:
3094:
3090:
3086:
3080:
3077:
3066:
3062:
3058:
3052:
3049:
3038:
3034:
3030:
3024:
3021:
3009:
3003:
3000:
2996:
2985:
2979:
2976:
2965:
2961:
2957:
2951:
2948:
2937:
2933:
2929:
2923:
2920:
2908:
2904:
2898:
2895:
2883:
2879:
2875:
2869:
2867:
2863:
2852:on 2020-01-09
2848:
2844:
2837:
2836:
2828:
2826:
2824:
2820:
2805:
2801:
2794:
2793:
2786:
2783:
2778:
2774:
2773:
2766:
2763:
2751:
2744:
2737:
2735:
2731:
2726:
2722:
2721:
2713:
2710:
2706:. p. 70.
2705:
2701:
2700:
2692:
2689:
2681:
2677:
2670:
2669:
2662:
2659:
2654:
2650:
2649:
2642:
2640:
2636:
2625:on 2017-11-07
2624:
2620:
2616:
2615:
2608:
2606:
2602:
2597:
2593:
2589:
2588:
2581:
2578:
2563:
2559:
2552:
2546:
2543:
2538:
2531:
2530:
2523:
2520:
2514:
2510:
2509:
2502:
2500:
2496:
2491:
2484:
2483:
2476:
2474:
2470:
2459:on 2017-10-25
2455:
2451:
2444:
2438:
2435:
2424:
2420:
2416:
2410:
2407:
2395:
2391:
2385:
2383:
2379:
2375:
2371:
2366:
2363:
2356:
2346:
2342:
2339:
2336:
2333:
2330:
2327:
2323:
2320:
2319:
2315:
2312:
2306:
2303:
2296:
2292:
2291:Leading digit
2289:
2287:
2284:
2282:
2279:
2277:
2276:Trailing zero
2274:
2271:
2268:
2267:
2263:
2261:
2259:
2255:
2251:
2247:
2243:
2239:
2234:
2228:
2224:
2220:
2215:
2213:
2209:
2204:
2202:
2197:
2178:
2176:
2172:
2168:
2164:
2160:
2152:
2143:
2141:
2137:
2133:
2129:
2125:
2124:normalization
2117:
1949:
1943:
1938:
1934:
1928:
1924:
1920:
1917:clz4 (x)
1916:
1911:
1907:
1905:
1897:
1893:
1889:
1885:
1881:
1877:
1873:
1869:
1866:clz3 (x)
1865:
1861:
1852:
1848:
1844:
1840:
1837:clz2 (x)
1836:
1832:
1826:
1822:
1818:
1814:
1811:clz1 (x)
1810:
1806:
1799:
1797:
1791:
1788:ctz5 (x)
1787:
1783:
1779:
1775:
1771:
1769:
1765:
1758:
1754:
1750:
1745:
1741:
1737:
1733:
1729:
1725:
1721:
1717:
1714:ctz3 (x)
1713:
1709:
1706:
1705:binary search
1701:
1699:
1695:
1691:
1684:
1680:
1677:
1673:
1669:
1666:ctz2 (x)
1665:
1661:
1657:
1652:
1649:
1647:
1643:
1636:
1632:
1628:
1624:
1621:ctz1 (x)
1620:
1616:
1610:
1608:
1601:
1597:
1593:
1589:
1585:
1581:
1578:x = 0 return
1577:
1574:pow2(x):
1573:
1569:
1564:The function
1559:
1557:
1554:
1550:
1548:
1547:binary search
1544:
1543:linear search
1535:
1533:
1507:
1502:
1499:
1492:
1488:
1481:
1477:, produce an
1475:
1469:
1449:
1445:
1441:
1438:) = popcount(
1437:
1432:
1427:
1423:
1419:
1411:
1407:
1403:
1398:
1397:
1396:
1390:
1382:
1378:
1360:
1355:
1354:
1353:
1326:
1322:
1318:
1313:
1312:
1311:
1304:
1293:
1289:
1283:
1278:
1273:
1259:
1255:
1247:
1242:
1241:
1240:
1229:
1225:
1221:
1217:
1213:
1191:
1180:
1176:
1166:
1160:
1158:
1152:unsigned int,
1147:
1144:
1127:
1121:
1118:
1117:
1113:
1110:
1105:
1102:
1093:
1087:
1084:
1083:
1079:
1076:
1073:
1070:
1061:
1059:
1056:
1055:
1051:
1046:
1045:
1041:
1039:
1024:
1022:
1017:
1013:
1011:
1008:
1005:
996:
994:
991:
990:
986:
983:
979:
976:
973:
968:
965:
964:Visual Studio
962:
961:
957:
954:
950:
946:
942:unsigned int,
939:
936:
931:
928:
927:Visual Studio
925:
924:
920:
917:
912:
909:
900:
897:
896:Visual Studio
894:
893:
889:
886:
878:unsigned int,
877:
874:
870:__builtin_ctz
866:__builtin_clz
862:__builtin_ffs
860:
857:
852:
849:
848:
844:
842:
839:
836:
827:
824:
821:
820:
816:
813:
808:
805:
792:
787:
784:
783:
779:
776:
772:
769:
766:
761:
756:
751:
748:
747:
743:
740:
738:Input type(s)
737:
734:
731:
728:
727:
724:
717:
715:
707:
704:
702:8, 16, 32, 64
701:
698:
695:
694:
690:
687:
685:8, 16, 32, 64
684:
681:
678:
677:
673:
670:
667:
664:
661:
659:
655:
651:
648:
645:
642:
639:
637:
634:
633:
629:
626:
623:
620:
617:
615:
612:
611:
607:
604:
601:
598:
595:
594:
590:
587:
584:
581:
578:
575:
571:
567:
564:
561:
558:
556:cnttzw/cnttzd
555:
553:
550:
549:
545:
542:
539:
536:
533:
531:
527:
523:
520:
519:
515:
512:
509:
506:
503:
501:
498:
497:
493:
490:
487:
484:
481:
478:
475:
474:
470:
467:
464:
461:
458:
457:
453:
450:
447:
444:
441:
439:
438:MIPS32/MIPS64
435:
431:
428:
425:
422:
419:
417:
414:
413:
409:
406:
403:
400:
397:
395:
391:
388:
387:
383:
380:
377:
374:
371:
369:
365:
361:
358:
357:
353:
350:
347:
344:
341:
340:
336:
333:
330:
327:
324:
321:
317:
313:
310:
307:
304:
301:
300:
296:
293:
290:
287:
284:
282:
278:
274:
271:
268:
265:
262:
260:
257:
256:
252:
249:
246:
243:
240:
237:
233:
230:
229:
225:
222:
219:
216:
213:
211:
205:
201:
198:
197:
193:
190:
187:
184:
181:
178:
177:
174:
172:
167:
159:
157:
153:
147:
146:
145:
142:
135:
134:
133:
127:
125:
123:
119:
115:
110:
108:
104:
100:
96:
92:
88:
77:
73:
69:
65:
61:
57:
53:
49:
48:bit operation
45:
41:
37:
33:
19:
3856:. Retrieved
3816:
3794:. Retrieved
3774:
3767:
3756:. Retrieved
3737:
3726:Gosper, Bill
3720:
3708:
3663:
3653:
3641:
3629:
3617:
3594:
3588:
3572:
3556:
3545:. Retrieved
3524:
3513:. Retrieved
3485:
3433:
3422:. Retrieved
3413:
3403:
3377:
3364:
3359:
3332:
3325:
3296:
3267:. Retrieved
3263:
3254:
3243:. Retrieved
3234:
3227:
3216:. Retrieved
3211:
3202:
3185:
3179:
3165:
3159:
3148:. Retrieved
3135:
3124:. Retrieved
3116:
3107:
3096:. Retrieved
3088:
3079:
3068:. Retrieved
3060:
3051:
3040:. Retrieved
3032:
3023:
3012:. Retrieved
3002:
2994:
2988:. Retrieved
2978:
2959:
2950:
2931:
2922:
2911:. Retrieved
2906:
2897:
2886:. Retrieved
2877:
2854:. Retrieved
2847:the original
2834:
2811:. Retrieved
2791:
2785:
2771:
2765:
2754:. Retrieved
2749:
2719:
2712:
2698:
2691:
2680:the original
2667:
2661:
2647:
2627:. Retrieved
2623:the original
2613:
2586:
2580:
2569:. Retrieved
2545:
2528:
2522:
2507:
2481:
2461:. Retrieved
2454:the original
2437:
2426:. Retrieved
2418:
2409:
2398:. Retrieved
2393:
2365:
2337:
2331:
2325:
2321:
2314:
2305:
2281:Leading zero
2257:
2253:
2245:
2241:
2235:
2227:Linux kernel
2216:
2205:
2198:
2186:(xy)⌉ ≤ ⌈log
2179:
2162:
2150:
2144:
2131:
2127:
2123:
2121:
2118:Applications
1946:
1941:
1936:
1931:
1926:
1922:
1918:
1914:
1908:
1900:
1895:
1891:
1887:
1883:
1879:
1875:
1871:
1867:
1863:
1855:
1850:
1846:
1842:
1838:
1834:
1829:
1824:
1820:
1816:
1812:
1808:
1803:
1794:
1789:
1785:
1781:
1777:
1773:
1761:
1756:
1752:
1748:
1743:
1739:
1735:
1731:
1727:
1723:
1719:
1715:
1711:
1702:
1689:
1687:
1682:
1678:
1675:
1671:
1667:
1663:
1659:
1655:
1650:
1645:
1641:
1639:
1634:
1630:
1626:
1622:
1618:
1614:
1605:
1595:
1591:
1587:
1583:
1579:
1575:
1571:
1563:
1555:
1551:
1539:
1503:
1497:
1490:
1486:
1479:
1473:
1470:
1455:
1443:
1439:
1435:
1425:
1421:
1417:
1409:
1405:
1401:
1395:, there is:
1374:
1358:
1332:
1324:
1320:
1319:) = w − clz(
1316:
1305:
1291:
1287:
1281:
1275:denotes the
1271:
1264:
1257:
1253:
1245:
1230:
1226:
1219:
1215:
1211:
1189:
1178:
1174:
1170:
977:unsigned int
729:Tool/library
721:
713:
166:instructions
163:
154:
151:
143:
139:
131:
111:
102:
98:
94:
90:
71:
67:
63:
59:
55:
52:machine word
43:
39:
35:
30:In computer
29:
3305:. pp.
2882:Apple, Inc.
2190:(x)⌉ + ⌈log
1496:1 <<
1344:operators,
1124:<bit>
1067:llvm.cttz.*
1063:llvm.ctlz.*
392:supporting
362:supporting
320:Intel 80386
191:Description
3897:Categories
3869:log base 2
3858:2012-01-03
3796:2020-01-09
3758:2020-01-09
3547:2020-01-09
3515:2020-01-09
3424:2020-01-09
3269:2020-05-25
3245:2020-05-25
3218:2016-02-23
3150:2020-04-03
3126:2022-05-09
3098:2012-01-03
3070:2018-05-21
3042:2018-05-21
3014:2017-04-09
2990:2017-04-09
2969:2015-11-14
2967:Retrieved
2941:2015-11-14
2939:Retrieved
2913:2012-01-04
2888:2012-01-04
2884:1994-04-19
2856:2020-01-10
2813:2020-01-09
2756:2020-01-09
2629:2012-01-04
2571:2014-01-02
2463:2016-10-22
2428:2012-01-03
2400:2012-01-02
2357:References
2256:) at step
2177:integers.
2019:0x43300000
1853:r + table
1506:bit arrays
1483:such that
1367:returning
1218:− 1 − clz(
1014:Undefined
921:Undefined
491:Log base 2
404:16, 32, 64
378:16, 32, 64
351:Log base 2
348:16, 32, 64
331:16, 32, 64
322:and later
85:. This is
72:log base 2
3668:CiteSeerX
3121:Microsoft
3093:Microsoft
3065:Microsoft
3037:Microsoft
2960:GCC 3.4.0
2250:Gray code
2219:bit array
2165:, a fast
1133:bit_width
1090:Data.Bits
1071:Intrinsic
1030:Functions
884:uintmax_t
840:long long
773:Includes
530:Power ISA
488:Arbitrary
479:and later
281:DEC Alpha
3852:Archived
3787:Archived
3752:Archived
3577:Anderson
3561:Anderson
3538:Archived
3506:Archived
3438:Anderson
3418:Archived
3395:Archived
2903:"FFS(3)"
2874:"FFS(3)"
2804:Archived
2676:Motorola
2596:Archived
2562:Archived
2390:"FFS(3)"
2370:Anderson
2264:See also
2082:>>
1977:unsigned
1937:function
1919:for each
1915:function
1904:L1 cache
1864:function
1835:function
1809:function
1786:function
1753:function
1712:function
1698:unrolled
1664:function
1619:function
1588:for each
1572:function
1389:Blackfin
1361:− ctz(2)
1177:) = ffs(
970:_arm_clz
890:0 (ffs)
825:7.1 libc
788:5.3 libc
182:Mnemonic
179:Platform
128:Examples
32:software
3732:(ed.).
3700:7545142
2779:. 2011.
2100:// log2
1662:0..2-1
1584:invalid
1580:invalid
1248:) = log
1019:Nvidia
933:__lzcnt
823:FreeBSD
786:FreeBSD
526:PowerPC
416:Itanium
208:except
3831:
3739:HAKMEM
3713:Warren
3698:
3688:
3670:
3646:Warren
3634:Warren
3622:Warren
3605:
3478:Warren
3461:Warren
3347:
3313:
3194:NVIDIA
2777:Oracle
2750:Github
2490:Compaq
2112:// CLZ
1989:double
1942:return
1929:table
1927:return
1906:miss.
1896:return
1872:return
1870:x = 0
1851:return
1843:return
1841:x = 0
1825:return
1817:return
1815:x = 0
1792:table
1790:return
1757:return
1744:return
1720:return
1718:x = 0
1683:return
1672:return
1670:x = 0
1635:return
1627:return
1625:x = 0
1598:x + 1
1596:return
1456:where
1412:) − 1)
1408:&
1357:clz =
1323:&
1290:&
1265:where
1256:&
755:4.3BSD
602:32, 64
585:32, 64
574:RISC-V
562:32, 64
540:32, 64
500:PDP-10
465:32, 64
448:32, 64
247:32, 64
120:or in
3790:(PDF)
3779:(PDF)
3696:S2CID
3541:(PDF)
3534:(PDF)
3509:(PDF)
3502:(PDF)
3291:(PDF)
3239:(PDF)
3190:(PDF)
3171:Intel
3145:Intel
2850:(PDF)
2839:(PDF)
2807:(PDF)
2796:(PDF)
2746:(PDF)
2683:(PDF)
2672:(PDF)
2592:Intel
2565:(PDF)
2554:(PDF)
2533:(PDF)
2513:Intel
2486:(PDF)
2457:(PDF)
2446:(PDF)
2297:Notes
2094:0x3FF
1971:union
1847:while
1821:while
1631:while
1414:, or
1381:SPARC
1267:&
1181:) − 1
1120:C++20
1048:__ffs
1026:__clz
856:Clang
853:3.4.0
833:flsll
829:ffsll
775:glibc
750:POSIX
741:Notes
662:flogr
522:POWER
482:bfffo
398:tzcnt
372:lzcnt
259:AVR32
107:POSIX
97:) or
62:) or
46:is a
42:) or
3867:and
3829:ISBN
3686:ISBN
3603:ISBN
3345:ISBN
3311:ISBN
2206:The
2194:(y)⌉
2182:⌈log
1860:n):
1778:from
1676:loop
1489:) =
1485:ctz(
1442:^ ~−
1434:ffs(
1416:ctz(
1400:ctz(
1393:ONES
1385:POPC
1315:ffs(
1244:ctz(
1214:) =
1173:ctz(
1058:LLVM
1021:CUDA
966:2012
949:BMI1
929:2008
898:2005
811:long
809:int,
802:flsl
794:ffsl
757:libc
735:Type
732:Name
696:vctz
679:vclz
646:0–32
504:jffo
394:BMI1
364:BMI1
302:cttz
285:ctlz
185:Name
83:(x)⌋
79:⌊log
3678:doi
3307:231
2843:IBM
2725:IBM
2704:IBM
2423:ARM
2326:ffz
1980:int
1962:int
1953:int
1944:r;
1800:CLZ
1774:for
1656:for
1611:CTZ
1602:FFS
1582://
1530:cto
1526:clo
1522:ffz
1518:clz
1514:ctz
1510:ffs
1501:).
1391:'s
1387:or
1383:'s
1365:ctz
1350:ctz
1346:clz
1342:clz
1340:or
1335:log
1308:ffs
1279:of
1237:ctz
1206:log
1202:clz
1195:log
1086:GHC
1042:32
1009:int
953:ABM
951:or
858:5.x
851:GCC
798:fls
770:int
763:ffs
705:ctz
688:clz
674:64
671:clz
649:ctz
640:ffs
636:VAX
630:64
627:clz
605:ctz
596:ctz
588:clz
579:clz
565:ctz
543:clz
513:clz
468:clo
459:clo
451:clz
442:clz
432:64
429:clz
420:clz
407:ctz
390:x86
381:clz
368:ABM
366:or
360:x86
342:bsr
334:ctz
325:bsf
314:64
311:ctz
297:64
294:clz
275:32
272:clz
263:clz
250:clz
241:clz
232:ARM
226:32
223:clz
214:clz
200:ARM
173:).
103:nlz
95:clz
89:to
68:ntz
60:ctz
40:ffs
3899::
3871:.)
3850:.
3846:.
3824:-
3781:.
3746:,
3736:.
3694:.
3684:.
3676:.
3579:.
3563:.
3536:.
3493:;
3468:^
3449:^
3440:.
3416:.
3412:.
3393:.
3389:.
3385:.
3340:-
3309:.
3293:.
3278:^
3262:.
3210:.
3169:.
3143:.
3119:.
3115:.
3091:.
3087:.
3063:.
3059:.
3035:.
3031:.
2993:.
2962:.
2958:.
2934:.
2930:.
2905:.
2880:.
2876:.
2865:^
2822:^
2798:.
2775:.
2748:.
2733:^
2723:.
2638:^
2604:^
2498:^
2488:.
2472:^
2421:.
2417:.
2392:.
2381:^
2372:.
2260:.
2217:A
2214:.
2196:.
2106:++
2085:20
2055:-=
1923:in
1921:y
1898:n
1892:if
1888:if
1884:if
1880:if
1876:if
1868:if
1839:if
1827:r
1813:if
1782:to
1780:0
1776:i
1746:n
1740:if
1736:if
1732:if
1728:if
1724:if
1716:if
1703:A
1679:if
1668:if
1660:in
1658:i
1637:r
1623:if
1592:in
1590:y
1576:if
1545:,
1528:,
1524:,
1516:,
1512:,
1428:))
1426:−x
1424:|
1410:−x
1325:−x
1292:−x
1272:−x
1258:−x
1224:.
1052:0
987:?
845:0
817:0
780:0
668:64
624:64
510:36
426:64
308:64
291:64
269:32
220:32
124:.
3861:.
3799:.
3761:.
3702:.
3680::
3611:.
3583:.
3567:.
3550:.
3518:.
3444:.
3427:.
3319:.
3272:.
3248:.
3221:.
3153:.
3129:.
3101:.
3073:.
3045:.
3017:.
2972:.
2944:.
2916:.
2891:.
2859:.
2816:.
2759:.
2632:.
2574:.
2466:.
2431:.
2403:.
2376:.
2347:.
2324:(
2258:k
2254:k
2246:k
2242:k
2192:2
2188:2
2184:2
2151:n
2132:m
2128:m
2109:;
2103:r
2097:;
2091:-
2088:)
2079:u
2076:.
2073:t
2070:(
2067:=
2064:r
2061:;
2052:d
2049:.
2046:t
2043:;
2040:x
2037:=
2034:u
2031:.
2028:t
2022:;
2016:=
2013:u
2010:.
2007:t
2004:;
2001:t
1998:}
1995:;
1992:d
1986:;
1983:u
1974:{
1968:;
1965:r
1959:;
1956:x
1858:2
1690:n
1646:n
1644:(
1642:O
1566:2
1560:2
1498:i
1491:i
1487:x
1480:x
1474:i
1466:~
1462:|
1458:^
1446:)
1444:x
1440:x
1436:x
1430:,
1422:x
1418:x
1406:x
1402:x
1369:w
1359:w
1337:2
1329:.
1327:)
1321:x
1317:x
1301:1
1297:1
1288:x
1282:x
1260:)
1254:x
1252:(
1250:2
1246:x
1233:2
1222:)
1220:x
1216:w
1212:x
1210:(
1208:2
1197:2
1190:w
1185:0
1179:x
1175:x
984:.
955:.
528:/
524:/
238:)
234:(
206:)
202:(
101:(
93:(
81:2
66:(
58:(
38:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.