src/ctz.hpp

View this file on GitHub
Last update: 2021-01-31 19:19:57+09:00
Include: #include "src/ctz.hpp"

Depends on

src/popcount.hpp

Required by

src/Prime.hpp

Verified with

test/aoj/ALDS1_1_C.test.cpp
test/aoj/ALDS1_1_C_2.test.cpp
test/own/Random_ctz.test.cpp
test/yosupo/enumerate_primes.test.cpp

Code

#pragma once

#include "popcount.hpp"

using lint = long long;

inline int ctz(lint n) {
    return popcount(~n & (n - 1));
}

#line 2 "src/ctz.hpp"

#line 2 "src/popcount.hpp"

using lint = long long;

inline int popcount(lint n) {
    n = (n & 0x5555555555555555) + (n >> 1 & 0x5555555555555555);
    n = (n & 0x3333333333333333) + (n >> 2 & 0x3333333333333333);
    n = (n & 0x0f0f0f0f0f0f0f0f) + (n >> 4 & 0x0f0f0f0f0f0f0f0f);
    n = (n & 0x00ff00ff00ff00ff) + (n >> 8 & 0x00ff00ff00ff00ff);
    n = (n & 0x0000ffff0000ffff) + (n >> 16 & 0x0000ffff0000ffff);
    n = (n & 0x00000000ffffffff) + (n >> 32 & 0x00000000ffffffff);
    return n;
}
#line 4 "src/ctz.hpp"

using lint = long long;

inline int ctz(lint n) {
    return popcount(~n & (n - 1));
}