{"id":4065,"date":"2026-09-01T12:31:27","date_gmt":"2026-09-01T11:31:27","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/?p=4065"},"modified":"2026-09-01T12:31:28","modified_gmt":"2026-09-01T11:31:28","slug":"bit-twiddling","status":"publish","type":"post","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/bit-twiddling\/","title":{"rendered":"Bit Twiddling"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Here are some bit manipulation identities that can be helpful to writing efficient code. In the below, we assume variables are 32 or 64-bit integers. Think C code.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Primitives used are integer arithmetic (+, -, *, \/) and logical bitwise operations (&amp;, |, ^, ~), and logical shift (&lt;&lt;, &gt;&gt;).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">lzcnt computes the number of leading zeros, tzcnt computes the number of trailing zeros. pdep(p,m) deposits the bits of p onto the non-zero positions of m. pext(p,m) extracts the bits from p indicated by a 1-bit in m into consecutive bit positions, filling as many as bits set in m.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">bzhi(a,k) clears all but the least significant k bits in a.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">See also <a href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/simd-bit-twiddling-hacks\/\" data-type=\"post\" data-id=\"2730\">SIMD Bit Twiddling Hacks<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Operations on multiple lzcnt and tzcnt calls<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>min( lzcnt( a ), lzcnt( b ) ) = lzcnt( a | b )<\/li>\n\n\n\n<li>min( tzcnt( a ), tzcnt( b ) ) = tzcnt( a | b )<\/li>\n\n\n\n<li>tzcnt( a ) + tzcnt( b ) = tzcnt( a * b )<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Extracting up to k 1-bits from a word<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The following codes keep the selected bits in the positions of the 1-bits in w, i.e., the result is a copy of w with only the least significant k 1-bits of w retained. All other bits are zero.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>pdep( (1&lt;&lt;k)-1, w )<\/li>\n\n\n\n<li>pdep( bzhi( ~0, k ), w )<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">One can also compact these bits in consecutive least-significant bit positions, resulting in a sequence of at most k consecutive 1-bits. For s = pdep( bzhi( ~0, k ), w ):<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>pext( s, w ) = bzhi( ~0, popcnt( s ) ) = (1&lt;&lt;k)-1<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Finding the bit position of the k-th set bit in a word<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">We assume k starts counting at zero, i.e., the 0-th 1-bit in 001010 is at position 1 (from lsb) and the 10th bit is at position 3.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>tzcnt( pdep( 1&lt;&lt;k, w ) )<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Here are some bit manipulation identities that can be helpful to writing efficient code. In the below, we assume variables are 32 or 64-bit integers. Think C code. Primitives used are integer arithmetic (+, -, *, \/) and logical bitwise operations (&amp;, |, ^, ~), and logical shift (&lt;&lt;, &gt;&gt;). lzcnt computes the number of [&hellip;]<\/p>\n","protected":false},"author":974,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[127],"tags":[],"class_list":["post-4065","post","type-post","status-publish","format-standard","category-technical-posts","czr-hentry"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/4065","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/users\/974"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/comments?post=4065"}],"version-history":[{"count":10,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/4065\/revisions"}],"predecessor-version":[{"id":4077,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/4065\/revisions\/4077"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=4065"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/categories?post=4065"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/tags?post=4065"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}