<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/76810>76810</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Basic checks against count-leading/trailing zeroes should be optimized
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          Validark
      </td>
    </tr>
</table>

<pre>
    Here are some basic transformations applicable on architectures lacking fast clz/ctz instructions: [Godbolt link](https://zig.godbolt.org/z/re4bfMGnc)

```zig
const T = u64;

export fn isCountLeadingZeroesEven1(x: T) bool {
    return 1 == @clz(x) & 1;
}

export fn isCountLeadingZeroesEven2(x: T) bool {
    const odd_bits: @TypeOf(x) =
@bitCast(@as(@Vector(@divExact(@bitSizeOf(@TypeOf(x)), 8), u8), @splat(0xaa)));
    return (x & ~odd_bits) > (x & odd_bits);
}
```

The previous code [[1](https://github.com/ziglang/zig/blob/9a56228c2b90d94d01bb76784c77fdec5710cf0a/lib/std/priority_dequeue.zig#L72), [2](https://github.com/google/guava/blob/3a86a13223b899b848a7f95556601d49d2faf426/guava/src/com/google/common/collect/MinMaxPriorityQueue.java#L502)] is actually useful for Atkinson et al.'s 1986 [Min-Max Heap](https://www.researchgate.net/profile/M-Atkinson/publication/220424085_Min-Max_Heaps_and_Generalized_Priority_Queues/links/00b49514bc2c945127000000/Min-Max-Heaps-and-Generalized-Priority-Queues.pdf) for telling whether a layer is a min layer or max layer. Here is an analogous transformation for count-trailing zeroes:

```zig
const T = u64;

export fn isCountTrailingZeroesEven1(x: u64) bool {
    return 1 == @ctz(x) & 1;
}

export fn isCountTrailingZeroesEven2(x: u64) bool {
    const odd_bits: @TypeOf(x) =
@bitCast(@as(@Vector(@divExact(@bitSizeOf(@TypeOf(x)), 8), u8), @splat(0xaa)));
    return ((x & (~x +% 1)) & odd_bits) != 0;
}
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzUVk1z2zgS_TXQBSUVCIJfBx2iOEoOce1urSuHvagaYJNCDAFaALRlHfLbpwBKtpNxJTNTcxkVSwAJ9Hvdj81HQgh6tIhrUm1IdbOAKe6dX38Bo3vw9wvp-qf1J_RIwSMN7oBUQtCKRg82DM4fIGpnA4Xj0WgF0iB1loJXex1RxcljoAbUvbYjHSBEqsyZ8K2KZ6ptiH5SOZ6U7yipNh9dL52J1Gh7T6obwtt9jMe0SviW8O1Zj6tx3rNyfkxXCN96FHK4_WgV4R1hN4S9u_zXbD7OepyvKGdDpHeUlDd0qgUpN6_34-nofKSDpTq8d5ONnxF6bcf_oXcYPjygLQhvTynXO8I7Kp0zlDQXDEop9Rgnb2mRCBIHESzX257SfsJrWrxwNjd_jpz_gnwuzvX9Tuo4KyrY3dMR_zU8Z1BeOQWTOr6HEAlviWAQ5vELquj8PO_1w4cTqMsOqeN_9XnG-hE3H-9pexmn64QIFo4GEgI7AVx3ds8avNIsQWWFvj1XkBP-8LLyauENFa83-7Wod3ukR48P2k2BKtcjzX2-Kd5qrlHH_SRXyh3mTjNgx3lG-FYaJwnfdlDVnLeKy471nehZIWVTN61QTTP0qKqmYGpgQPjW6BQQYk_49ui18zo-7Xr8_4QTrjJo-bnhV6WqDf9lTqNzo8E0meABXpIqoa2hKDkvZdt1shUtNENXVVVds6IXXc8HGASvX0UGr9JT-D2scoeDs3liDKYbv73V9hZO_76k_5-c-9cMUX6uWM6-uqE6UFBxAmOe6BRwmAwdnKfv4r22wVmKkYJZEd4EWnRtnaq91XZ5Cyf6CeH4VuGPj48rjwGTk4wQcWUxZiHdoHOyt8srfLo8yeQ-yUoI33LOBBesrXYXll1iCTuw_e4jWvRg9Bn73bWsXa4r5Htm79PImBRdVQipuOpEVfCG5d-sSIJcZsgl2H75CnJ5hVzOkKtjP6Q2TmpENCa54OMe4x49BWrgCX0Wjx60vZw6Tw9wmk9WNFtv2mEpWDBuTI38vfdmcJUcYxk96MxxzqaRxPw77fDuAv-GH6boP-yI8S864u_5-S_5__Gm-Ox-hLff0mxDeEWLOeZHW6SEF0ll9hN_XPTrsu_KDha4LhomeFuWFV_s17LDth0EV4IhKBQVilopWQ5t1VWl6Bd6zRkXrGBlwRnn1WqQdVFzqHvVYy0VJ4LhAbRZGfNwSC_ohQ5hwnVTtwVbGJBoQv7S4NziI82LhCfjW_h1ilnKaQxEMKNDDC8oUUeD603-8FB7VPeBwgjp--HS-GZ-VxK-_eERoGHvJtNTidQdoz6kh3QxebP-ic0m2suwPHr3dXbCnGzyhlzMbwEAAP__ayPJEw">