फाइंड फर्स्ट सेट

कंप्यूटर सॉफ़्टवेयर और हार्डवेयर में, पहला सेट (FFS) ढूंढें या पहला सेट ढूंढें एक बिट ऑपरेशन है, जिसे एक अहस्ताक्षरित शब्द (कंप्यूटर वास्तुकला) दिया गया है,कम से कम महत्वपूर्ण बिट स्थिति से शब्द गणना में एक पर सेट किए गए कम से कम महत्वपूर्ण बिट के सूचकांक या स्थिति को निर्दिष्ट करता है। लगभग समतुल्य ऑपरेशन अनुगामी शून्यों (ctz) या अनुगामी शून्यों की संख्या (ntz) की गणना है, जो कम से कम महत्वपूर्ण एक बिट के बाद शून्य बिट्स की संख्या की गणना करता है। पूरक ऑपरेशन जो सबसे महत्वपूर्ण सेट बिट के सूचकांक या स्थिति का पता लगाता है, लॉग बेस 2 है, इसलिए इसे इसलिए कहा जाता है क्योंकि यह द्विआधारी लघुगणक की गणना करता है ⌊log₂(x)⌋.यह अग्रणी शून्य (सीएलजेड) या अग्रणी शून्य की संख्या (एनएलजेड) की गणना करने के लिए #गुण और संबंध है, जो सबसे महत्वपूर्ण एक बिट से पहले शून्य बिट्स की संख्या की गणना करता है।पहले सेट को खोजने के दो सामान्य प्रकार हैं, POSIX परिभाषा जो 1 पर बिट्स का अनुक्रमण शुरू करती है,यहां एफएफएस लेबल किया गया है, और वह वेरिएंट जो शून्य पर बिट्स का अनुक्रमण शुरू करता है, जो सीटीजेड के बराबर है और इसलिए उसे उस नाम से बुलाया जाएगा।

अधिकांश आधुनिक सीपीयू अनुदेश सेट वास्तुकला इनमें से एक या अधिक को हार्डवेयर ऑपरेटर के रूप में प्रदान करते हैं; सॉफ़्टवेयर अनुकरण आम तौर पर उन सभी के लिए प्रदान किया जाता है जो उपलब्ध नहीं हैं, या तो कंपाइलर इंट्रिनिक्स के रूप में या सिस्टम लाइब्रेरीज़ में।

उदाहरण

निम्नलिखित 32-बिट शब्द दिया गया है:

0000 0000 0000 0000 1000 0000 0000 1000

गिनती के पीछे शून्य ऑपरेशन 3 लौटाएगा, जबकि गिनती अग्रणी शून्य ऑपरेशन 16 लौटाएगा। गिनती अग्रणी शून्य ऑपरेशन शब्द आकार पर निर्भर करता है: यदि इस 32-बिट शब्द को 16-बिट शब्द में छोटा कर दिया गया था, तो गिनती अग्रणी शून्य शून्य वापस आएगा . पहला सेट ढूंढें ऑपरेशन 4 लौटाएगा, जो दाईं ओर से चौथी स्थिति को दर्शाता है। लॉग बेस 2 15 है।

इसी प्रकार, निम्नलिखित 32-बिट शब्द को देखते हुए, उपरोक्त शब्द का बिटवाइज़ निषेध:

1111 1111 1111 1111 0111 1111 1111 0111

काउंट ट्रेलिंग वन्स ऑपरेशन 3 लौटाएगा, काउंट लीडिंग वन्स ऑपरेशन 16 लौटाएगा, और फाइंड फर्स्ट जीरो ऑपरेशन ffz 4 लौटाएगा।

यदि शब्द शून्य है (कोई बिट्स सेट नहीं है), तो अग्रणी शून्यों की गिनती करें और पिछले शून्यों की गिनती करें, दोनों शब्द में बिट्स की संख्या लौटाते हैं, जबकि एफएफएस शून्य लौटाता है। लॉग बेस 2 और फाइंड फर्स्ट सेट के शून्य-आधारित कार्यान्वयन दोनों आम तौर पर शून्य शब्द के लिए एक अपरिभाषित परिणाम लौटाते हैं।

हार्डवेयर समर्थन

कई आर्किटेक्चर में नीचे सूचीबद्ध पहले सेट और/या संबंधित संचालन को तेजी से निष्पादित करने के लिए निर्देश सेट शामिल हैं। सबसे आम ऑपरेशन गिनती अग्रणी शून्य (सीएलजेड) है, संभवतः क्योंकि अन्य सभी ऑपरेशन इसके संदर्भ में कुशलतापूर्वक कार्यान्वित किए जा सकते हैं (#गुण और संबंध देखें)।

Platform	Mnemonic	Name	Operand widths	Description	On application to 0
ARM (ARMv5T architecture and later) except Cortex-M0/M0+/M1/M23	clz	Count Leading Zeros	32	clz	32
ARM (ARMv8-A architecture)	clz	Count Leading Zeros	32, 64	clz	Operand width
AVR32	clz	Count Leading Zeros	32	clz	32
DEC Alpha	ctlz	Count Leading Zeros	64	clz	64
	cttz	Count Trailing Zeros	64	ctz	64
Intel 80386 and later	bsf	Bit Scan Forward	16, 32, 64	ctz	Undefined; sets zero flag
	bsr	Bit Scan Reverse	16, 32, 64	Log base 2	Undefined; sets zero flag
x86 supporting BMI1 or ABM	lzcnt	Count Leading Zeros	16, 32, 64	clz	Operand width; sets carry flag
x86 supporting BMI1	tzcnt	Count Trailing Zeros	16, 32, 64	ctz	Operand width; sets carry flag
Itanium	clz	Count Leading Zeros	64	clz	64
MIPS32/MIPS64	clz	Count Leading Zeros in Word	32, 64	clz	Operand width
	clo	Count Leading Ones in Word	32, 64	clo	Operand width
Motorola 68020 and later	bfffo	Find First One in Bit Field	Arbitrary	Log base 2	Field offset + field width
PDP-10	jffo	Jump if Find First One	36	ctz	0; no operation
POWER/PowerPC/Power ISA	cntlz/cntlzw/cntlzd	Count Leading Zeros	32, 64	clz	Operand width
Power ISA 3.0 and later	cnttzw/cnttzd	Count Trailing Zeros	32, 64	ctz	Operand width
RISC-V ("B" Extension) (draft)	clz	Count Leading Zeros	32, 64	clz	Operand width
	ctz	Count Trailing Zeros	32, 64	ctz	Operand width
SPARC Oracle Architecture 2011 and later	lzcnt (synonym: lzd)	Leading Zero Count	64	clz	64
VAX	ffs	Find First Set	0–32	ctz	Operand width; sets zero flag
IBM z/Architecture	flogr	Find Leftmost One	64	clz	64
	vclz	Vector Count Leading Zeroes	8, 16, 32, 64	clz	Operand width
	vctz	Vector Count Trailing Zeroes	8, 16, 32, 64	ctz	Operand width

कुछ अल्फ़ा प्लेटफ़ॉर्म पर CTLZ और CTTZ का सॉफ़्टवेयर में अनुकरण किया जाता है।

उपकरण और पुस्तकालय समर्थन

कई कंपाइलर और लाइब्रेरी विक्रेता पहले सेट और/या संबंधित संचालन को खोजने के लिए कंपाइलर इंट्रिनिक्स या लाइब्रेरी फ़ंक्शंस की आपूर्ति करते हैं, जिन्हें अक्सर उपरोक्त हार्डवेयर निर्देशों के संदर्भ में कार्यान्वित किया जाता है:

Tool/library	Name	Type	Input type(s)	Notes	On application to 0
POSIX.1 compliant libc 4.3BSD libc OS X 10.3 libc	ffs	Library function	int	Includes glibc. POSIX does not supply the complementary log base 2 / clz.	0
FreeBSD 5.3 libc OS X 10.4 libc	ffsl fls flsl	Library function	int, long	fls("find last set") computes (log base 2) + 1.	0
FreeBSD 7.1 libc	ffsll flsll	Library function	long long		0
GCC 3.4.0 Clang 5.x	__builtin_ffs[l,ll,imax] __builtin_clz[l,ll,imax] __builtin_ctz[l,ll,imax]	Built-in functions	unsigned int, unsigned long, unsigned long long, uintmax_t	GCC documentation considers result undefined clz and ctz on 0.	0 (ffs)
Visual Studio 2005	_BitScanForward _BitScanReverse	Compiler intrinsics	unsigned long, unsigned __int64	Separate return value to indicate zero input	Undefined
Visual Studio 2008	__lzcnt	Compiler intrinsic	unsigned short, unsigned int, unsigned __int64	Relies on hardware support for the lzcnt instruction introduced in BMI1 or ABM.	Operand width
Visual Studio 2012	_arm_clz	Compiler intrinsic	unsigned int	Relies on hardware support for the clz instruction introduced in the ARMv5T architecture and later.	?
Intel C++ Compiler	_bit_scan_forward _bit_scan_reverse	Compiler intrinsics	int		Undefined
NVIDIA CUDA	__clz	Functions	32-bit, 64-bit	Compiles to fewer instructions on the GeForce 400 Series	32
	__ffs				0
LLVM	llvm.ctlz.* llvm.cttz.*	Intrinsic	8, 16, 32, 64, 256	LLVM assembly language	Operand width, if 2nd argument is 0; undefined otherwise
GHC 7.10 (base 4.8), in Data.Bits	countLeadingZeros countTrailingZeros	Library function	FiniteBits b => b	Haskell programming language	Operand width
C++20 standard library, in header <bit>	bit_ceil bit_floor bit_width countl_zero countl_one countr_zero countr_one	Library function	unsigned char, unsigned short, unsigned int, unsigned long, unsigned long long

गुण और संबंध

यदि बिट्स को 1 से शुरू करके लेबल किया गया है (जो कि इस आलेख में प्रयुक्त परंपरा है), तो अनुगामी शून्यों की गणना करें और पता लगाएं कि पहले सेट ऑपरेशन किससे संबंधित हैं ctz(x) = ffs(x) − 1 (सिवाय जब इनपुट शून्य हो)। यदि बिट्स को प्रारंभ से लेबल किया गया है 0, फिर पिछले शून्यों की गिनती करें और पता लगाएं कि पहला सेट बिल्कुल समतुल्य संचालन है। दिया गया w प्रति शब्द बिट्स, log₂ से आसानी से गणना की जा सकती है clz और इसके विपरीत log₂(x) = w − 1 − clz(x).

जैसा कि ऊपर दिए गए उदाहरण में दिखाया गया है, पहले शून्य ढूंढें, अग्रणी शून्य गिनें, और अनुगामी शून्य गिनें संचालन को इनपुट को अस्वीकार करके और पहले सेट ढूंढें, अग्रणी शून्य गिनें, और अनुगामी शून्य गिनें का उपयोग करके कार्यान्वित किया जा सकता है। विपरीत भी सही है।

कुशल लॉग वाले प्लेटफ़ॉर्म पर₂ M68000 जैसे ऑपरेशन, ctz द्वारा गणना की जा सकती है:

ctz(x) = log₂(x & −x)

कहाँ & बिटवाइज़ AND और को दर्शाता है −x दोनों के पूरक को दर्शाता है x. इजहार x & −x न्यूनतम-महत्वपूर्ण को छोड़कर सभी को साफ़ करता है 1 बिट, ताकि सबसे अधिक- और सबसे कम-महत्वपूर्ण 1 बिट समान हैं.

एआरएम और पावरपीसी जैसे कुशल गिनती अग्रणी शून्य संचालन वाले प्लेटफार्मों पर, ffs द्वारा गणना की जा सकती है:

ffs(x) = w − clz(x & −x).

इसके विपरीत, बिना मशीनों पर log₂ या clz ऑपरेटर, clz का उपयोग करके गणना की जा सकती है ctz, यद्यपि अकुशलता से:

clz = w − ctz(2^{⌈log₂(x)⌉}) (जिस पर निर्भर करता है ctz लौट रहा हूँ w शून्य इनपुट के लिए)

SPARC जैसे कुशल हथौड़ा चलाना वजन (जनसंख्या गणना) ऑपरेशन वाले प्लेटफार्मों पर POPCया Blackfin का ONES,वहाँ है:

ctz(x) = popcount((x & −x) − 1),या ctz(x) = popcount(~(x | −x)),

ffs(x) = popcount(x ^ ~−x): clz = 32 − popcount(2^{⌈log₂(x)⌉} − 1)

कहाँ ^ बिटवाइज़ एक्सक्लूसिव-OR को दर्शाता है, | बिटवाइज़ OR और को दर्शाता है ~ बिटवाइज़ नकार को दर्शाता है।

उलटा समस्या (दिया गया है i, एक उत्पादन करें x ऐसा है कि ctz(x) = i) की गणना बाईं-शिफ्ट के साथ की जा सकती है (1 << i).

पहला सेट ढूंढें और संबंधित संचालन को एक छोर से शुरू करके और एक शब्द तक आगे बढ़ते हुए सीधे तरीके से मनमाने ढंग से बड़े बिट सरणी तक बढ़ाया जा सकता है जो कि पूर्ण-शून्य नहीं है (के लिए) ffs, ctz, clz) या सभी-एक नहीं (के लिए)। ffz, clo, cto) का सामना करना पड़ता है। एक ट्री डेटा संरचना जो पुनरावर्ती रूप से बिटमैप का उपयोग करके ट्रैक करती है कि कौन से शब्द गैर-शून्य हैं, इसे तेज कर सकते हैं।

सॉफ़्टवेयर अनुकरण

1980 के दशक के उत्तरार्ध के अधिकांश सीपीयू में एफएफएस या समकक्ष के लिए बिट ऑपरेटर होते हैं, लेकिन एआरएम-एमएक्स श्रृंखला जैसे कुछ आधुनिक सीपीयू में ऐसा नहीं होता है। एफएफएस, सीएलजेड और सीटीजेड के लिए हार्डवेयर ऑपरेटरों के बदले में, सॉफ्टवेयर उन्हें शिफ्ट, पूर्णांक अंकगणित और बिटवाइज़ ऑपरेटरों के साथ अनुकरण कर सकता है। सीपीयू की वास्तुकला और कुछ हद तक प्रोग्रामिंग भाषा के शब्दार्थ और कंपाइलर कोड पीढ़ी की गुणवत्ता के आधार पर कई दृष्टिकोण हैं। दृष्टिकोणों को शिथिल रूप से रैखिक खोज के रूप में वर्णित किया जा सकता है, द्विआधारी खोज, खोज+टेबल लुकअप, डी ब्रुइज़न गुणन, फ़्लोटिंग पॉइंट रूपांतरण/प्रतिपादक अर्क, और बिट ऑपरेटर (शाखा रहित) तरीके. निष्पादन समय और भंडारण स्थान के साथ-साथ पोर्टेबिलिटी और दक्षता के बीच भी विरोधाभास है।

सॉफ़्टवेयर अनुकरण आमतौर पर नियतात्मक होते हैं। वे सभी इनपुट मानों के लिए एक परिभाषित परिणाम लौटाते हैं; विशेष रूप से, सभी शून्य बिट्स के इनपुट का परिणाम आम तौर पर एफएफएस के लिए 0 होता है, और अन्य परिचालनों के लिए ऑपरेंड की बिट लंबाई होती है।

यदि किसी के पास हार्डवेयर सीएलजेड या समकक्ष है, तो सीटीजेड को बिट ऑपरेशंस के साथ कुशलतापूर्वक गणना की जा सकती है, लेकिन इसका विपरीत सच नहीं है: हार्डवेयर ऑपरेटर की अनुपस्थिति में सीएलजेड गणना करने में कुशल नहीं है।

2ⁿ

कार्यक्रम 2^{⌈log₂(x)⌉} (दो की निकटतम घात तक पूर्णांकित करें) शिफ्ट और बिटवाइज़ ओआरएस का उपयोग करकेइस 32-बिट उदाहरण की तरह गणना करना कुशल नहीं है और यदि हमारे पास 64-बिट या 128-बिट ऑपरेंड है तो यह और भी अधिक अक्षम है:

फ़ंक्शन pow2(x):
  यदि x = 0 वापसी अमान्य // अमान्य कार्यान्वयन परिभाषित है ([0,63] में नहीं)
  एक्स ← एक्स - 1
  {1, 2, 4, 8, 16} में प्रत्येक y के लिए: x ← x | (एक्स >> वाई)
  वापसी x + 1

एफएफएस

चूँकि ffs = ctz + 1 (POSIX) या ffs = ctz (अन्य कार्यान्वयन), ctz के लिए लागू एल्गोरिदम का उपयोग किया जा सकता है, जिसके परिणाम में 1 जोड़ने का संभावित अंतिम चरण होता है, और इनपुट के लिए ऑपरेंड लंबाई के बजाय 0 लौटाता है। सभी शून्य बिट्स.

CTZ

कैनोनिकल एल्गोरिदम एलएसबी से शुरू होने वाले शून्यों की गिनती करने वाला एक लूप है जब तक कि 1-बिट का सामना न हो जाए:

फ़ंक्शन ctz1 (x)
  यदि x = 0 वापसी w
  टी ← 1
  आर ← 0
  जबकि (x & t) = 0
    टी ← टी << 1
    आर ← आर + 1
  वापसी आर

यह एल्गोरिदम O(n) समय और संचालन निष्पादित करता है, और बड़ी संख्या में सशर्त शाखाओं के कारण व्यवहार में अव्यावहारिक है।

एक लुकअप तालिका अधिकांश शाखाओं को समाप्त कर सकती है:

तालिका[0..2n-1] = ctz(i) i के लिए 0..2 मेंn-1
फ़ंक्शन ctz2 (x)
  यदि x = 0 वापसी w
  आर ← 0
  कुंडली
    अगर (एक्स और (2n-1)) ≠ 0
      वापसी आर + तालिका [एक्स और (2n-1)]
    x ← x >> n
    आर ← आर + एन

पैरामीटर n निश्चित है (आमतौर पर 8) और समय-स्थान ट्रेडऑफ़ का प्रतिनिधित्व करता है। लूप पूरी तरह से लूप का खुलना भी हो सकता है। लेकिन एक रैखिक लुकअप के रूप में, ऑपरेंड में बिट्स की संख्या में यह दृष्टिकोण अभी भी O(n) है।

एक बाइनरी खोज कार्यान्वयन संचालन और शाखाओं की एक लघुगणकीय संख्या लेता है, जैसा कि इस 32-बिट संस्करण में है:इस एल्गोरिदम को एक तालिका द्वारा भी सहायता प्रदान की जा सकती है, जो एक सूचकांक के रूप में सामने आए पहले गैर-शून्य बाइट का उपयोग करके 256 प्रविष्टि लुकअप तालिका के साथ नीचे के तीन यदि कथनों को प्रतिस्थापित करती है।

फ़ंक्शन ctz3 (x)
  यदि x = 0 है तो 32 लौटें
  एन ← 0
  यदि (x और 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16
  यदि (x और 0x000000FF) = 0: n ← n + 8, x ← x >> 8
  यदि (x और 0x0000000F) = 0: n ← n + 4, x ← x >> 4
  यदि (x और 0x00000003) = 0: n ← n + 2, x ← x >> 2
  यदि (x और 0x00000001) = 0: n ← n + 1
  वापसी एन

यदि हार्डवेयर में clz ऑपरेटर है, तो ctz की गणना करने का सबसे कुशल तरीका इस प्रकार है:

फ़ंक्शन ctz4 (x)
  एक्स &= -एक्स
  वापसी w - (clz(x) + 1)

32-बिट सीटीज़ के लिए एक एल्गोरिदम एक न्यूनतम सही हैश फ़ंक्शन बनाने के लिए डी ब्रुइज़न अनुक्रमों का उपयोग करता है जो सभी शाखाओं को समाप्त करता है।यह एल्गोरिदम मानता है कि गुणन के परिणाम को 32 बिट तक छोटा कर दिया गया है।

i के लिए 0 से 31 तक: तालिका[( 0x077CB531 * (1 << i ) ) >> 27 ] ← i // तालिका [0..31] आरंभीकृत
फ़ंक्शन ctz5 (x)
  वापसी तालिका[((x & -x) * 0x077CB531) >> 27]

अभिव्यक्ति (x & -x) फिर से सबसे कम महत्वपूर्ण 1 बिट को अलग करती है। तब केवल 32 संभावित शब्द हैं, जिन्हें अहस्ताक्षरित गुणन और हैश को तालिका में सही स्थिति में स्थानांतरित किया जाता है। (यह एल्गोरिदम शून्य इनपुट को संभाल नहीं पाता है।)

कल्ज़

कैनोनिकल एल्गोरिदम एमएसबी से शुरू करके एक समय में एक बिट की जांच करता है जब तक कि एक गैर-शून्य बिट नहीं मिल जाता, जैसा कि इस उदाहरण में दिखाया गया है। यह O(n) समय में निष्पादित होता है जहां n ऑपरेंड की बिट-लंबाई है, और सामान्य उपयोग के लिए एक व्यावहारिक एल्गोरिदम नहीं है।

फ़ंक्शन clz1 (x)
  यदि x = 0 वापसी w
  टी ← 1 << (डब्ल्यू - 1)
  आर ← 0
  जबकि (x & t) = 0
    टी ← टी >> 1
    आर ← आर + 1
  वापसी आर

पिछले लूपिंग दृष्टिकोण में सुधार एक समय में आठ बिट्स की जांच करता है और फिर 256 (2) का उपयोग करता है⁸) पहले गैर-शून्य बाइट के लिए प्रविष्टि लुकअप तालिका। हालाँकि, यह दृष्टिकोण निष्पादन समय में अभी भी O(n) है।

फ़ंक्शन clz2 (x)
  यदि x = 0 वापसी w
  t ← 0xff << (w - 8)
  आर ← 0
  जबकि (x & t) = 0
    टी ← टी >> 8
    आर ← आर + 8
  रिटर्न आर + टेबल[x >> (डब्ल्यू - 8 - आर)]

बाइनरी खोज निष्पादन समय को घटाकर O(लॉग) कर सकती है₂एन):

फ़ंक्शन clz3 (x)
  यदि x = 0 है तो 32 लौटें
  एन ← 0
  यदि (x और 0xFFFF0000) = 0: n ← n + 16, x ← x << 16
  यदि (x और 0xFF000000) = 0: n ← n + 8, x ← x << 8
  यदि (x और 0xF0000000) = 0: n ← n + 4, x ← x << 4
  यदि (x और 0xC0000000) = 0: n ← n + 2, x ← x << 2
  यदि (x और 0x80000000) = 0: n ← n + 1
  वापसी एन

सीएलज़ को अनुकरण करने के लिए सबसे तेज़ पोर्टेबल दृष्टिकोण बाइनरी सर्च और टेबल लुकअप का संयोजन है: एक 8-बिट टेबल लुकअप (2)⁸=256 1-बाइट प्रविष्टियाँ) बाइनरी खोज में नीचे की 3 शाखाओं को प्रतिस्थापित कर सकती हैं। 64-बिट ऑपरेंड को एक अतिरिक्त शाखा की आवश्यकता होती है। बड़ी चौड़ाई वाले लुकअप का उपयोग किया जा सकता है लेकिन अधिकतम व्यावहारिक तालिका का आकार आधुनिक प्रोसेसर पर L1 डेटा कैश के आकार तक सीमित है, जो कई लोगों के लिए 32 KB है। किसी शाखा को सहेजना L1 कैश मिस की विलंबता से ऑफसेट से कहीं अधिक है।

CTZ के लिए डी ब्रुइज़न गुणन के समान एक एल्गोरिथ्म CLZ के लिए काम करता है, लेकिन सबसे महत्वपूर्ण बिट को अलग करने के बजाय, यह फॉर्म 2 के निकटतम पूर्णांक तक पूर्णांक बनाता हैⁿ−1 शिफ्ट और बिटवाइज़ ORs का उपयोग करना:

तालिका[0..31] = {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}
फ़ंक्शन clz4 (x)
  {1, 2, 4, 8, 16} में प्रत्येक y के लिए: x ← x | (एक्स >> वाई)
  वापसी तालिका[((x * 0x07C4ACDD) >> 27) % 32]

गहरे पाइपलाइन वाले प्रोसेसर के लिए, जैसे प्रेस्कॉट और बाद के इंटेल प्रोसेसर, गलत पूर्वानुमानित शाखाओं के लिए पाइपलाइन फ्लश से बचने के लिए शाखाओं को बिटवाइज़ AND और OR ऑपरेटरों (भले ही कई और निर्देशों की आवश्यकता होती है) द्वारा प्रतिस्थापित करना तेज़ हो सकता है (और इस प्रकार की शाखाएं हैं) स्वाभाविक रूप से अप्रत्याशित):

फ़ंक्शन clz5 (x)
  आर = (x > 0xFFFF) << 4; एक्स >>= आर;
  क्यू = (x > 0xFF ) << 3; एक्स >>= क्यू; आर |= क्यू;
  q = (x > 0xF ) << 2; एक्स >>= क्यू; आर |= क्यू;
  क्यू = (x > 0x3 ) << 1; एक्स >>= क्यू; आर |= क्यू;
                  आर |= (x >> 1);
  वापसी आर;

उन प्लेटफार्मों पर जो पूर्णांकों को फ़्लोटिंग पॉइंट में हार्डवेयर रूपांतरण प्रदान करते हैं, अग्रणी शून्य की गिनती की गणना करने के लिए घातांक फ़ील्ड को स्थिरांक से निकाला और घटाया जा सकता है। पूर्णांकन त्रुटियों को ध्यान में रखते हुए सुधार की आवश्यकता है।फ़्लोटिंग पॉइंट रूपांतरण में पर्याप्त विलंबता हो सकती है। यह विधि अत्यधिक गैर-पोर्टेबल है और आमतौर पर इसकी अनुशंसा नहीं की जाती है।

int x; 
int r;
union { unsigned int u[2]; double d; } t;

t.u[LE] = 0x43300000;  // LE is 1 for little-endian
t.u[!LE] = x;
t.d -= 4503599627370496.0;
r = (t.u[LE] >> 20) - 0x3FF;  // log2
r++;  // CLZ

अनुप्रयोग

सामान्यीकरण को कुशलतापूर्वक लागू करने के लिए गिनती अग्रणी शून्य (सीएलजेड) ऑपरेशन का उपयोग किया जा सकता है, जो एक पूर्णांक को एम × 2 के रूप में एन्कोड करता है^e, जहां m का ज्ञात स्थिति में सबसे महत्वपूर्ण बिट है (जैसे कि उच्चतम स्थिति)। इसके बदले में इसका उपयोग न्यूटन-रेफसन डिवीजन को लागू करने, सॉफ्टवेयर और अन्य अनुप्रयोगों में पूर्णांक से तैरनेवाला स्थल रूपांतरण करने के लिए किया जा सकता है।

अग्रणी शून्यों की गणना करें (clz) का उपयोग पहचान के माध्यम से 32-बिट विधेय x = y (यदि सत्य है तो शून्य, यदि गलत है तो एक) की गणना करने के लिए किया जा सकता है clz(x − y) >> 5, जहां >> अहस्ताक्षरित दायां बदलाव है।इसका उपयोग अधिक परिष्कृत बिट संचालन करने के लिए किया जा सकता है जैसे n 1 बिट्स की पहली स्ट्रिंग ढूंढना।इजहार clz(x − y)1 << (16 − clz(x − 1)/2) न्यूटन की विधि का उपयोग करके 32-बिट पूर्णांक के वर्गमूल की गणना के लिए एक प्रभावी प्रारंभिक अनुमान है।सीएलजेड कुशलतापूर्वक शून्य दमन को कार्यान्वित कर सकता है, एक तेज़ डेटा संपीड़न तकनीक जो एक पूर्णांक को गैर-शून्य बाइट्स के साथ अग्रणी शून्य बाइट्स की संख्या के रूप में एन्कोड करती है।यह समान वितरण (असतत) पूर्णांकों का सीएलजेड लेकर कुशलतापूर्वक घातीय वितरण पूर्णांक उत्पन्न कर सकता है।

लॉग बेस 2 का उपयोग यह अनुमान लगाने के लिए किया जा सकता है कि गुणन अतिप्रवाह होगा या नहीं ⌈log₂(xy)⌉ ≤ ⌈log₂(x)⌉ + ⌈log₂(y)⌉.

गोस्पर के लूप-डिटेक्शन एल्गोरिदम को लागू करने के लिए अग्रणी शून्यों की गिनती और अनुगामी शून्यों की गिनती का एक साथ उपयोग किया जा सकता है,जो सीमित संसाधनों का उपयोग करके परिमित सीमा के किसी फ़ंक्शन की अवधि ज्ञात कर सकता है।

बाइनरी जीसीडी एल्गोरिदम पिछले शून्य को हटाने में कई चक्र खर्च करता है; इसे एक बदलाव के बाद शून्य के पीछे की गिनती (ctz) से बदला जा सकता है। एक समान लूप हेलस्टोन अनुक्रम की गणना में दिखाई देता है।

प्राथमिकता कतार को लागू करने के लिए एक बिट सरणी का उपयोग किया जा सकता है। इस संदर्भ में, फाइंड फर्स्ट सेट (एफएफएस) पॉप या पुल उच्चतम प्राथमिकता वाले तत्व ऑपरेशन को कुशलतापूर्वक लागू करने में उपयोगी है। लिनक्स कर्नेल रीयल-टाइम शेड्यूलर आंतरिक रूप से उपयोग करता है sched_find_first_bit() इस उद्देश्य से।

काउंट ट्रेलिंग शून्य ऑपरेशन हनोई टॉवर समस्या का एक सरल इष्टतम समाधान देता है: डिस्क को शून्य से क्रमांकित किया जाता है, और चाल k पर, डिस्क संख्या ctz(k) को दाईं ओर न्यूनतम संभव दूरी पर ले जाया जाता है (वापस चारों ओर चक्कर लगाते हुए) आवश्यकतानुसार छोड़ दिया गया)। यह एक मनमाना शब्द लेकर और चरण k पर बिट ctz(k) फ़्लिप करके एक ग्रे कोड भी उत्पन्न कर सकता है।

यह भी देखें

• इंटेल और एएमडी x86-आधारित प्रोसेसर के लिए बिट हेरफेर अनुदेश सेट (बीएमआई)।
• शून्य से पीछे चल रहा है
• मुख्य शून्य
• अनुगामी अंक
• अग्रणी अंक

अग्रिम पठन

• Warren, Jr., Henry S. (2013) [2002]. Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.
• Anderson, Sean Eron (2005) [1997]. "Bit Twiddling Hacks". Stanford University. Archived from the original on 2020-01-08. Retrieved 2012-01-03. (NB. Lists several efficient public domain C implementations for count trailing zeros and log base 2.)

बाहरी संबंध

• Intel Intrinsics Guide
• Chess Programming Wiki: BitScan: A detailed explanation of a number of implementation methods for ffs (called LS1B) and log base 2 (called MS1B).