Как узнать в каком бите байта - единица?

[Zeus]

Получаю байт с единицей в одном бите.
Нужно сформировать число которое будет содержать позицию единичного бита в исходном байте.
Но нумерация - обратная:
если единица в 7м бите - надо вернуть число 0.
если единица в 0м бите - надо вернуть число 7.

Всякое циклическое наложение маски со сдвигом - это отношу к алгоритмическим методам, банально и долго работать будет (в среднем - 4 итерации).
Пока завёл std::map
Есть вариант со switch/case.

Можно это как-нибудь математически решить? Эффективнее (или не менее эффективно), чем перечисленные методы?

[t.t]

Математически это двоичный логарифм (: Только боюсь, если его представить в машииных операциях даже только для этих степеней двойки, всё равно неоптимально получится. Самое быстрое, что приходит в голову -- ассемблерный оператор сдвига вправо с вытеснением. На x86 он, помнится, однотактный, плюс один такт на сверку флага и один на условный переход. Итого 3*8=24 такта. Ещё запись значения -- но от неё всё равно никуда не денешься. Так что оптимальнее некуда, по-моему.

Добавлено: А, нет, вру. Можно вместо записи значения суммирование использовать -- тогда ещё быстрее будет.

[Voice]

если единица в 7м бите - надо вернуть число 0.
если единица в 0м бите - надо вернуть число 7.

Что-то другого алгоритма не наблюдается...

Код: Выделить всё

#include <stdio.h>

int main()
{
    unsigned char a = 16;
    unsigned char test = 128;
    int i;

    for(i = 0; i < 8; i++) {
        if(test & a) {
            printf("Found! bit: %d\n", i);
            return 0;
        }

        test = test >> 1;
    }

    return 0;
}

Если так важна скорость то можно inline процедуру на ассемблере сделать.

[Zeus]

Не то чтобы нужна прям офигенная скорость, но хотелось бы красивого и оптимального решения.

[MiK13]

А какие критерии по памяти?
Потому, что если не жалко лишних 256 байт памяти, то можно сделать:

Код: Выделить всё

typedef unsigned char byte;
static char tb[256] = { 8,7,6,8,5,8,8,8,4,[9 ... 15]=8,3,[17 ... 31]=8,2,[33 ... 63]=8,1,[65 ... 127]=8,0,[129 ... 255]=8};
int nb;        // Номер бита
byte b;        // Сам байт
   ...
  nb = tb[b];

Если в байте нет единичных битов или их больше одного результат будет равен 8.
Если нужен номер самого левого/правого елиничного бита, то достаточно будет изменить таблицу tb

P.S. т.к тип char знаковый, то можно вместо 8 использовать -1. -- легче проверять на некорректные значения.

[Grom]

Быстро, но коряво и не оптимально по размеру кода, наверное, так:

int main()
{

unsigded char data[256] ;

data[1] = 128;
data[2] = 64;
data[4] = 32;
data[8] = 16;
data[16] = 8;
data[32] = 4;
data[64] = 2;
data[128] = 1;

unsigned char test;

read( socket, test, sizeof(test) ) ; // или ещё как получаем данное значение

printf("%d\n"data[test]) ;

return 0;
}

[Zeus]

Ну да, массив, наверное, самое быстрое.
Даже быстрее switch/case.
Не сказать, правда, что самое красивое решение...
Зато по ограничениям задачи, не обязательно инициализировать все элементы

[MiK13]

Зато по ограничениям задачи, не обязательно инициализировать все элементы

Ну, элементы всегда инициализируются, вопрос только в том чем? Обычно, если не указано иное, то нулём.
Но в условии задачи было:

если единица в 7м бите - надо вернуть число 0.
если единица в 0м бите - надо вернуть число 7.

Поэтому любой байт с числом единичных битов не равным 1 даст результат аналогичный значению 0x80. И поэтому я бы сделал так:

Код: Выделить всё

static char tb[256] = { 0,8,7,0,6,0,0,0,5,[16]=4,[32]=3,[64]=2,[128]=1};
  ...
  nb = tb[b]-1;                    // Номер бита

Тогда отрицательное значение nb указывало бы на некорректный байт.
Если некорректные байты в принципе невозможны, то задаваемые значения таблицы можно уменьшить на 1

[RasenHerz]

на x86 асме есть операция возвращающая положение певого старшего бита в числе, к сожалению не помню точно что именно за операция.
может гуру асма подскажут=)

[BlackStar]

ffs?

[t.t]

на x86 асме есть операция возвращающая положение певого старшего бита в числе, к сожалению не помню точно что именно за операция.
может гуру асма подскажут=)

О, точно. Только по-моему, она уже на 486 появилась. Или путаю?.. Давно дело было, не помню ничего уже...

[Zeus]

Асм - тоже интересно.
Но всё-таки хотелось бы чего-то переносимого и на плюсах

[t.t]

Ну как Вам сказать... У меня те масштабы времени, которые можно сэкономить на такой задаче (т.е. единицы, максимум десятки тактов) как-то автоматически с ассемблером ассоциируются. (;

[sarutobi]

самое быстрое - массивом - одна выборка + 256 байт памяти. Все остальное будет гораздо менее красивым - потребуется как минимум 8 операций сдвига с суммированием

[BlackStar]

Код: Выделить всё

#include <stdio.h>
#include <string.h>

int main()
{
    int n;
    unsigned char data[8];

    data[1] = 128;
    data[2] = 64;
    data[3] = 32;
    data[4] = 16;
    data[5] = 8;
    data[6] = 4;
    data[7] = 2;
    data[8] = 1;

    n = ffs(4); // Здесь приходящий байт!

    printf("Result: %d\n", data[n]);
    return 0;
}

Как вам такой вариант? Памяти теперь 8 байт.

[t.t]

Как вам такой вариант? Памяти теперь 8 байт.

Только у этого варианта на входе номер бита, на выходе единица в этом бите. А надо наоборот.

[Crazy]

Мой бредовый вариант
конъюнкция 01000100 и 01000000 даст 0100000
10110101 и 01000000 даст 00000000

[t.t]

Собственно, если уж идёт речь не об ассемблере, а о C++, решил померять:

Код: Выделить всё

t:~/tmp/test$ cat 1.c
int main() {
  unsigned char test,d[129],nil;
  long i;
  for(test=0; test<8; test++)
    d[1<<test]=test;
  for(i=0; i<=10000000; i++)
    for(test=1; test>0; test*=2)
      nil=d[test];
  return 0;
}
t:~/tmp/test$ gcc 1.c && time ./a.out

real    0m0.713s
user    0m0.676s
sys     0m0.008s

Код: Выделить всё

t:~/tmp/test$ cat 2.c
int main() {
  unsigned char test,nil,t;
  long i;
  for(i=0; i<=10000000; i++)
    for(test=1; test>0; test*=2) {
      nil=0; t=test;
      while(t>>=1)
        nil++;
    }
  return 0;
}
t:~/tmp/test$ gcc 2.c && time ./a.out

real    0m3.358s
user    0m3.348s
sys     0m0.004s

Т.е. выборка из массива чуть меньше чем впятеро быстрее сдвига, даже если пренебречь накладными расходами на цикл. Но. Даже восемьдесят миллионов сдвигов -- это меньше чем три с половиной секунды.

[Crazy]

К массиву можно применить бинарный алгоритм поиска, число шагов log2(8)=3.
Сдвиг и деление на 2, очень дешевые операции.

А смысл в этом есть?

[whirlwind]

сдвиги у меня получились самые долгие, 18 секунд, потом swicth (12 cек) и выборка из массива (8 сек).

кстати, массив нужно обьявлять d[129], есть такое

[minoru-kun]

Всякое циклическое наложение маски со сдвигом - это отношу к алгоритмическим методам, банально и долго работать будет (в среднем - 4 итерации).

Как бывшый ассемблерист, заявляю, что все подобные операции выполняются любой машиной крайне быстро

[Grom]

...
Поэтому любой байт с числом единичных битов не равным 1 даст результат аналогичный значению 0x80.
...

Прошу прощения, но в постановке задачи явно было сказано:

Получаю байт с единицей в одном бите.

[minoru-kun]

Кстати, да, логарифмическая выборка отлично применяется к данной задаче. Можно даже без сдвигов.
Пусть функция f (W, q1, q2) изменяет состояние автомата на q1, если утверждение W истинно, q2, если ложно.
Мн-во состояний автомата - {0, 0l, 0r, 0ll, 0lr, 0rl, 0rr, f0..f7}, 0 - начальное состояние, f0..f7 - конечные.

Код: Выделить всё

0: f (а И 2^4-1 = 0) 0l 0r

0l: f (а И (2^2-1)*4 = 0) 0ll 0lr #Если автомат пришел в это состояние, то битик находится где-то на интервале [4,7] разрядов
0r: f (а И 2^2-1 = 0) 0rl 0rr #битик находится на интервале [0,3] разрадов

0ll: (а И 2^6 = 0) f7 f6
0lr: (a И 2^4 = 0) f5 f4
0rl: (а И 2^2 = 0) f3 f2
0rr: (а Т 2^0 = 0) f1 f0

#Ура! Пришли в конечное состояние. Расшифровка:
f0: бит #0
f1: бит #1
<...>

Представляя сей автомат в виде орграфа типа "деревяшка" и подписывая маски в их двоичной записи около каждой вершины замечаем, что:

• Распознается любое a не превосходящее 2^8-1 (и эти результаты будут верны, если a содержит лишь 1 бит)
• Для любого a достаточно лишь 3-х сравнений по маске, чтобы придти в конечное состояние

[t.t]

К массиву можно применить бинарный алгоритм поиска, число шагов log2(8)=3.
Сдвиг и деление на 2, очень дешевые операции.

А смысл в этом есть?

Если 128 байт памяти не жалко, то не думаю. Я сейчас вот ещё пустой цикл посчитал:

Код: Выделить всё

t:~/tmp/test$ cat 0.c
int main() {
  unsigned char test;
  long i;
  for(i=0; i<=10000000; i++)
    for(test=1; test>0; test*=2);
  return 0;
}
t:~/tmp/test$ gcc-4.1 0.c && time ./a.out

real    0m0.551s
user    0m0.548s
sys     0m0.000s

Т.е. сама выборка из массива, за вычетом цикла -- порядка 160 миллисекунд на 80 миллионов повторений. Бытрее, по-моему, только на ассемблере.

кстати, массив нужно обьявлять d[129], есть такое

Конечно, спасибо. Техническая ошибка; уже исправил.

[NickLion]

Упоминали про ассемблер, но так ничего и не сказали, примерно так:

bsf eax, dword ptr [data] ; собственно определяет позицию младшей единицы
;jz _нет_единиц_ ; если надо
neg eax
add eax, 7
mov dword ptr [res], eax

коротко и сурово... но надо ли так страдать? ведь переносимость кода снижается...

PS есть еще и bsr - берет позицию старшей единицы, но позиция все-равно отсчитывается от младших разрядов

[minoru-kun]

А чем плох способ с конечным автоматом?
Припрягать всякие x86-специфичные инструкции - значит забить на переносимость.

[AestheteAnimus]

Вот и мои 5 копеек:

Код: Выделить всё

ssize_t bit_index(uint8_t x)
{
    if (x == 0)  return -1;

    int n = 0;
    if (x > 0xF)  {n += 4; x >>= 4; }
    if (x > 0x3)  {n += 2; x >>= 2; }
    if (x > 0x1)  {n += 1;}

    return n;
}

Соответственно, вот листинг того, что получилось (оптимизация Os):

Код: Выделить всё

ssize_t bit_index(uint8_t x)
{
 80483f4:    55                       push   %ebp
    if (x == 0)  return -1;
 80483f5:    83 c8 ff                 or     $0xffffffff,%eax
 80483f8:    89 e5                    mov    %esp,%ebp
 80483fa:    8a 55 08                 mov    0x8(%ebp),%dl
 80483fd:    84 d2                    test   %dl,%dl
 80483ff:    74 1d                    je     804841e <bit_index+0x2a>

    int n = 0;
    if (x > 0xF)  {n += 4; x >>= 4; }
 8048401:    31 c0                    xor    %eax,%eax
 8048403:    80 fa 0f                 cmp    $0xf,%dl
 8048406:    76 05                    jbe    804840d <bit_index+0x19>
 8048408:    c0 ea 04                 shr    $0x4,%dl
 804840b:    b0 04                    mov    $0x4,%al
    if (x > 0x3)  {n += 2; x >>= 2; }
 804840d:    80 fa 03                 cmp    $0x3,%dl
 8048410:    76 06                    jbe    8048418 <bit_index+0x24>
 8048412:    83 c0 02                 add    $0x2,%eax
 8048415:    c0 ea 02                 shr    $0x2,%dl
    if (x > 0x1)  {n += 1;}
 8048418:    80 fa 02                 cmp    $0x2,%dl
 804841b:    83 d8 ff                 sbb    $0xffffffff,%eax

    return n;
}
 804841e:    5d                       pop    %ebp
 804841f:    c3                       ret

[t.t]

Вот и мои 5 копеек:

Время замерить не могли бы, так же, как я это делал, -- чтобы сравнить?

[AestheteAnimus]

Время замерить не могли бы, так же, как я это делал, -- чтобы сравнить?

Смысл? Во-первых, у нас с Вами разные платформы, и если я что-то посчитаю, то это не позволит ничего сравнить. Во-вторых, достаточно глянуть листинги, чтобы увидеть, что версия с массивом быстрее. Ну лично мне такой подход не нравится, поэтому и предлагаю вариант с бинарным поиском.

[MiK13]

достаточно глянуть листинги, чтобы увидеть, что версия с массивом быстрее. Ну лично мне такой подход не нравится, поэтому и предлагаю вариант с бинарным поиском.

А чем именно не нравится?

Но код

Код: Выделить всё

ssize_t bit_index(uint8_t x)
{
    if (x == 0)  return -1;

    int n = 0;
    if (x > 0xF)  {n += 4; x >>= 4; }
    if (x > 0x3)  {n += 2; x >>= 2; }
    if (x > 0x1)  {n += 1;}

    return n;
}

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

Код: Выделить всё

 if (x > 0xF)  {n += 4; x >>= 4; }

а не

Код: Выделить всё

 if (x > 0xF)  {n = 4; x >>= 4; }

(учитывая что начальное значение равно нулю)
Но потом, посмотрев листинг ассемблера, увидел, что он сделал именно

Код: Выделить всё

 if (x > 0xF)  { x >>= 4; n=4; }

Прошу прощения, но в постановке задачи явно было сказано:

Получаю байт с единицей в одном бите.

Совершенно верно. И если в байте всегда будет только одна единица, то достаточно будет массива размером 128:

Код: Выделить всё

static char tb[128] = { 7,6,0,5,0,0,0,4,[15]=3,[31]=2,[63]=1};
   ...
 nb = tb[b-1];

Но такая программа не может считаться надёжной, т.к. не известен результат в случае, если число единиц в байте не будет равно 1. А это принципе возможно.