• Clemens Hammacher's avatar
    Reland "[bits] Consolidate Count{Leading,Trailing}Zeros" · 27ffc624
    Clemens Hammacher authored
    This is a reland of 7d231e57, fixed to
    avoid instantiating CountLeadingZeros for bits==0.
    
    Original change's description:
    > [bits] Consolidate Count{Leading,Trailing}Zeros
    > 
    > Instead of having one method for 32 bit integers and one for 64 bit,
    > plus a templatized version to choose from those two, just implement one
    > version which handles unsigned integers of any size. Also, make them
    > constexpr.
    > The Count{Leading,Trailing}Zeros{32,64} methods are kept for now in
    > order to keep the amount of code changes small. Also, sometimes it
    > improves readability by stating exactly the size of the argument,
    > especially for leading zeros (where zero-extending would add more
    > leading zeros).
    > 
    > CountLeadingZeros now uses a binary search inspired implementation
    > as proposed in Hacker's Delight. It's more than 20% faster on x64 if
    > the builtins are disabled.
    > CountTrailingZeros falls back to CountPopulation instead of counting in
    > a naive loop. This is ~50% faster.
    > 
    > R=mstarzinger@chromium.org
    > 
    > Change-Id: I1d8bf1d7295b930724163248150444bd17fbb34e
    > Reviewed-on: https://chromium-review.googlesource.com/741231
    > Reviewed-by: Michael Starzinger <mstarzinger@chromium.org>
    > Commit-Queue: Clemens Hammacher <clemensh@chromium.org>
    > Cr-Commit-Position: refs/heads/master@{#49106}
    
    Change-Id: Icdff2510ec66d1c96a1912cef29d77d8550994ee
    Reviewed-on: https://chromium-review.googlesource.com/753903Reviewed-by: 's avatarMichael Starzinger <mstarzinger@chromium.org>
    Commit-Queue: Clemens Hammacher <clemensh@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#49138}
    27ffc624
slot-set.h 21.1 KB