Перестановка битов: из ulong получить битовую маску, представляющую, какие байты отличны от нуля - PullRequest
Новая
       58

Перестановка битов: из ulong получить битовую маску, представляющую, какие байты отличны от нуля

1 голос
/ 10 июля 2019

Скажем, у нас есть 8-байтовый ulong. Для каждого байта мы хотим знать, является ли он нулевым или ненулевым. Желаемый результат - это байт, чьи 8 битов представляют «ненулевое значение» исходных 8 байтов.

Есть ли название для этой операции или набора операций?

Как мы можем достичь этого очень эффективно? Идеальное решение было бы без ответвлений.

В качестве альтернативного требования, полезным ответом будет позиция первого ненулевого байта. Например. если первый ненулевой байт является третьим, ответом будет 2 (индекс на основе 0). Я понимаю, что к этому можно приблизиться, посчитав начальные нули ответа первоначального требования, но, возможно, это позволит сократить путь.

Ответы [ 3 ]

1 голос
/ 10 июля 2019

Вы можете сдвинуть длинную на 8 битов и посмотреть на каждый байт независимо (т.е. проверить, равен ли байт == 0). Используя индекс байта, вы можете установить значение в результирующем байте, сдвинув 1 в этот битовый индекс. 

    private byte TestULong(ulong value)
    {
        byte result = 0;
        for (int i = 0; i < 8; i++)
        {
            var test = (byte)(value >> (i * 8));
            if (test != 0)
            {
                result = (byte)(result | (1 << i));
            }
        }
        return result;
    }
1 голос
/ 10 июля 2019

У меня есть ощущение, что к этому есть чисто математический подход, но я не могу разобраться в этом. В противном случае наиболее эффективный способ сделать это - использовать цикл и некоторые побитовые сравнения: 

public static byte Evaluate(ulong n) {
    ulong mask = 0xFF;
    byte result = 0;
    for (int i = 0; i < 8; i++) {
        if ((n & (mask << (i * 8))) != 0) {
            result |= (byte)(1 << i);
        }
    }
    return result;
}

Маска - это предварительно сконфигурированное значение, где каждый бит в одном байте равен 1 (255 в десятичном виде, FF в шестнадцатеричном). Вы смещаете маску на i * 8, чтобы она покрывала n-й байт ввода, а затем используете побитовое И для получения значения этого байта. Все, что вам нужно сделать, это проверить, не является ли это значение байта ненулевым, и если это так, установить соответствующий бит результирующего байта равным 1. (Это можно сделать с помощью сложения или побитового ИЛИ, поэтому я выбрал идти по маршруту ИЛИ, чтобы придерживаться побитовой темы.)

https://dotnetfiddle.net/EA7NRw

1 голос
/ 10 июля 2019

Это может помочь - 

    private void Evaluate(ulong n)
    {
        ulong f = 255;
        int r = 0, p = -1;
        for (int i = 0; i < 8; i++)
        {
            r >>= 1;
            var t = n & f;
            if (t > 0)
            {
                r += 128;
                if (p < 0)
                    p = i;
            }
            f <<= 8;
        }
        Console.WriteLine($"Resulting byte: {r}");
        Console.WriteLine($"Position: {p}");
    }

То, что я сделал, - это побитовое AND для каждого байта входного 8-байтового числа с 255 (1111 1111). Если результат равен единице, я сдвинул вправо один бит для результата и добавил 128 (1000 000).

Для позиции, которую я инициализировал p = -1, если номер равен нулю. В противном случае присвойте первому индексу `> 0 '.

Возможна большая оптимизация, например, сравнение входного числа с нулем и, если true, просто возвращает 0 для результата и -1 для позиции.

...