Parallel Deposit / Bit Scatter в Python. Есть ли оно вообще?

Question

Parallel Deposit / Bit Scatter в Python. Есть ли оно вообще?

Папа Высший разум (144030), открыт 2 недели назад

На этой неделе Литкод кошмарит индейцев битовыми операциями, в которые они не умеют.
https://leetcode.com/problems/minimum-array-end/description/

Нужно найти минимально возможное n-1-ое число строго возрастающей последовательности положительных чисел, AND всех элементов которой даёт заданное число x. Понятно, что нужно просто биты раскидать в свободные слоты этого самого икса.

Собственно, задача не особо сложная, минут за 15 решается при помощи интринсиков (вообще, за минуту, но не в моём возрасте и не в 4 часа ночи). Пока индийские друзья писали свои любимые циклы, слепил я на эту тему однострочник примерно такого вида:

 #include <immintrin.h>

#define BMI2 __attribute__((__target__("bmi2")))

class Solution {
public:
    static long long minEnd(const uint n, const uint x) BMI2 {
        return x | _pdep_u64(n - 1u, ~uint64_t(x));
    }
};

(для C и Rust - аналогично)

Java тоже приятно удивила. Мало того, что нашёлся метод, так он ещё и интринсифицирован в OpenJDK (и их JDK как раз LC и использует):

 class Solution {
    public static long minEnd(final int n, final int x) {
        return x | Long.expand(n - 1, ~(long)x);
    }
}

А вот в Питоне так не получается. Цикл, конечно, работает (медленная ручная реализация PDEP):

 class Solution:
    @staticmethod
    def minEnd(n: int, x: int) -> int:
        n -= 1
        c, m, mask = 0, 1, x ^ ((1 << (n.bit_length() + x.bit_length())) - 1)
        while mask:
            b = mask & -mask
            if n & m:
                c |= b
            mask -= b
            m <<= 1
        return x | c

и даже светит 0 ms / 100% в итогах выполнения.

Но есть ли способ решить это однострочником, без циклов, как в нормальных языках?

А тут - решение со ссылками на код. Всё, кроме Java, исполняется достаточно шустренько:
https://leetcode.com/problems/minimum-array-end/solutions/6024965/bit-deposit-one-liner-beating-100-in-c-c-rust-and-python/

Answer 1

Sergio 2.1 Оракул (67655) 2 недели назад

 class Solution: 
    @staticmethod 
    def minEnd(n: int, x: int) -> int: 
        return x | sum(((n - 1) >> i & 1) << p for p, i in enumerate(p for p in range(x.bit_length() + (n - 1).bit_length()) if not x & (1 << p)))

ПапаВысший разум (144030) 2 недели назад

Ну это тот же индийский цикл, только вытянутый в одну строчку. Медленно, громоздко. Причём если у меня цикл проходит только по нулевым битам икса, то тут - по всем битам x и по всем битам n-1.

Не, я искал что-то вроде bit_length(), bit_count() и т.п., чтобы можно было одним вызовом сделать депозит битов в нужные позиции, обозначенные маской.