C++20 added two new library features for those of you that like bit twiddling: \u201cbit rotating and counting functions\u201d and \u201cintegral power of two operations\u201d. Most of the added function templates are simple numeric utility functions, and a handful map somewhat directly to common instructions on modern CPUs. We’ve implemented them in Visual Studio 2019 version 16.8 Preview 2. This post will tell you about our implementations and what processor-specific optimizations you can expect.<\/p>\n
All the functions are fully constexpr enabled, which should be quite handy for things like computing lookup tables. I know I\u2019ve seen these functions implemented in several numeric codebases, so hopefully having standard versions will be useful. The new functions are:<\/p>\n
<\/p>\n
These count the number of zeros on the left (from most-significant-bit to least-significant-bit), or right (from least-significant-bit to most-significant-bit) respectively. On x86 and x64 platforms these emit the Interestingly, Note that Visual Studio version 16.8 Preview 1 contains a bug related to <\/p>\n <\/p>\n Counts the number of ones on the left or right of their input; these rely on <\/p>\n Functionally equivalent to <\/p>\n Finds the nearest power of two above or below the input. If the input is already a power of two it is returned unchanged. If the result would not be representable in the input\u2019s type, then the behavior is undefined (this occurs for example in <\/p>\n Bitwise rotates the input to the left or right. Currently this does not explicitly emit any special instructions.<\/p>\n <\/p>\n You can try all of these functions out today by downloading Visual Studio 2019 version 16.8 Preview 2<\/a>\u00a0 and compiling your code with You can also read find our reference documentation<\/a> or the relevant C++ papers on Bit twiddling: \u201cbit rotating and counting functions\u201d and \u201cintegral power of two operations\u201d.<\/p>\n","protected":false},"author":4807,"featured_media":35994,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-26344","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cplusplus"],"acf":[],"blog_post_summary":" Bit twiddling: \u201cbit rotating and counting functions\u201d and \u201cintegral power of two operations\u201d.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/26344","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/users\/4807"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/comments?post=26344"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/26344\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media\/35994"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media?parent=26344"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/categories?post=26344"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/tags?post=26344"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}LZCNT<\/code> and TZCNT<\/code> instructions respectively. By default, the availability of the instructions is checked at runtime. The BSF<\/code> and BSR<\/code> instructions will be used if the runtime check fails. The runtime check is omitted when compiling with \/arch:AVX2<\/code> or higher, since all CPUs that support AVX2 also support LZCNT<\/code> and TZCNT<\/code>. On ARM and ARM64 countl_zero<\/code> emits the CLZ<\/code> instruction; countr_zero<\/code> does not emit any special instructions on ARM<\/code> or ARM64<\/code> at this time.<\/p>\nLZCNT<\/code> and TZCNT<\/code> have a somewhat oddball instruction encoding on x86 and x64; they are encoded as REP BSF<\/code> and REP BSR<\/code>. The rep prefix is ignored on CPUs that don\u2019t support LZCNT<\/code> or TZCNT<\/code>. This means that running code with LZCNT<\/code> or TZCNT<\/code> on a CPU that doesn\u2019t support them will still run, but TZCNT<\/code> won\u2019t have the correct output for zero and LZCNT<\/code> will both have the wrong output for zero and return the index of the first set bit starting from the least significant bit, which is the opposite of what it does on CPUs that actually support the instruction. This isn\u2019t a very useful fallback, and while we tried to use it in <bit><\/code> to simplify some code, it ended up being more trouble than it was worth.<\/p>\nLZCNT<\/code> usage on CPUs that only support bsr. This will be fixed in Visual Studio version 16.8 Preview 3.<\/p>\nstd::popcount<\/h2>\n
std::popcount<\/code> counts the number of set bits in its input. On x86 and x64 platforms popcount<\/code> emits the POPCNT<\/code> instruction, again checking the availability of POPCNT<\/code> at runtime. If compiled with \/arch:AVX<\/code> or higher no check is made as all CPUs that support AVX also support POPCNT<\/code>. No special instructions are emitted on ARM or ARM64 at this time.<\/p>\nstd::countl_one, std::countr_one<\/h2>\n
countl_zero<\/code> and countr_zero<\/code> and thus will use the same intrinsics as those<\/p>\nstd::has_single_bit<\/h2>\n
popcount(x) == 1<\/code>. has_single_bit<\/code> does not use any special instructions.<\/p>\nstd::bit_ceil, std::bit_floor<\/h2>\n
bit_ceil(static_cast<unsigned char>(0b11111111))<\/code>). bit_ceil<\/code> is only allowed as a constant expression if this undefined behavior does not occur. bit_floor<\/code> returns zero when the input is zero.<\/p>\nstd::rotl, std::rotr<\/h2>\n
\/std:c++latest<\/code>. If you find any bugs in our library implementation report them by opening an issue at on our GitHub page<\/a>. Please report any other Visual Studio issues on Developer Community<\/a>. Don\u2019t hesitate to contact us with any questions or suggestions.<\/p>\n<bit><\/code>: P0553R4: Bit operations<\/a> and P0556R3: Integral power-of-2 operations<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"