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

[t.t]

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

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

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

Что быстрее -- понятно. Вопрос в том, насколько быстрее. Это могло бы дать понять, насколько вариант с массивом вообще оправдан, если исходить только из скорости.

Я не настаиваю. Если нет желания -- то зачем?.. У кого желание появится, тот и сравнит. А так можно действительно сравнить листинги и посчитать на пальцах.

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

Если проверка пишется для определённого контекста, в котором исходные данные таки известны, то разговоры о "надёжности при неизвестных исходных данных" мне напоминают шутку о теоретике, которому дали задачу посчитать устойчивость стола с четырьмя ножками.

[AestheteAnimus]

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

Лично мне жалко 128 байт большая часть из которых заведомо не будет использоваться. В случае, когда есть всего 1КБ это бывает актуально.

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

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

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

а не

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

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

(учитывая что начальное значение равно нулю)

В принципе это сделано для симметричности кода. А учитывая, что компилятор подобные вещи достаточно хорошо и ожидаемо оптимизирует - мы ничего не теряем.

Что быстрее -- понятно. Вопрос в том, насколько быстрее. Это могло бы дать понять, насколько вариант с массивом вообще оправдан, если исходить только из скорости.

Все таки я сделал проверку и был мягко говоря удивлен. Собственно, вот код:

Соответственно, вот результаты работы:

Подсчет времени накладных расходов (на цикл, на вызов функций)

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

time ./main

real    0m0.480s
user    0m0.477s
sys     0m0.000s

Последовательный перебор всех битов:

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

time ./main bitwise

real    0m1.137s
user    0m1.131s
sys     0m0.000s

Метод на свитч/кейсах. Может этот метод можно соптимизировать, но моя лобовая раулизация дает такой результат:

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

time ./main case

real    0m0.859s
user    0m0.856s
sys     0m0.000s

А вот метод с использованием массива. Полученные результаты меня удивили своей схожестью с предыдущим методом.

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

time ./main lookup

real    0m0.858s
user    0m0.855s
sys     0m0.001s

Наконец, предложенный мной метод:

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

time ./main search

real    0m0.616s
user    0m0.613s
sys     0m0.000s

Как не странно, но этот метод оказался эффективнее. В объективности своего теста я не уверен - так что не лишним будет его перепроверить.

UPD
Компилировал с оптимизацие O4

[MiK13]

Лично мне жалко 128 байт большая часть из которых заведомо не будет использоваться. В случае, когда есть всего 1КБ это бывает актуально.

Если в распоряжении всего1 КБ, я не вижу смысла использовать компилятор C, а не Ассемблер. И в этом случае, скорее всего, наиболее оптимальным вариантом будет простой сдвиг с определением переноса (если процессор не имеет инструкции определения номера младшего/старшего бита). И думать о переносимости кода на разные платформы я смысла не вижу.

Все таки я сделал проверку и был мягко говоря удивлен. Собственно, вот код:

Соответственно, вот результаты работы:
..................
Метод на свитч/кейсах. Может этот метод можно соптимизировать, но моя лобовая раулизация дает такой результат:

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

time ./main case
  ........

А вот метод с использованием массива. Полученные результаты меня удивили своей схожестью с предыдущим методом.

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

time ./main lookup
  ........

А вот фрагмент кода файла main.c:

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

        if (strcmp(argv[1], "case") == 0)
            method = bit_index_case;
        else if ( strcmp(argv[1], "lookup") == 0)
            method = bit_index_case;

Мои результаты теста:

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

$ time ./main
real    0m0.525s
user    0m0.492s
sys     0m0.004s

$ time ./main bitwise
real    0m1.077s
user    0m1.048s
sys     0m0.000s

$ time ./main case
real    0m0.796s
user    0m0.764s
sys     0m0.004s

$ time ./main lookup
real    0m0.539s
user    0m0.504s
sys     0m0.000s

$ time ./main search
real    0m0.742s
user    0m0.700s
sys     0m0.000s

Кстати, добавление ключа -O4 уменьшило время работы почтив два раза

[whirlwind]

Компилировал с оптимизацие O4

странно, в man gcc описываются уровни только до O3. Хотя интереса ради проверил, он и O8 скушал, не ругнулся
но вообще такого рода тесты правильно было бы компилировать с O0, иначе не факт, что в бинарник попадут ваши ухищрения, а не компиляторные...

[MiK13]

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

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

$ gcc -O0 -o main main.c
$ time ./main
real    0m0.776s
user    0m0.744s

$ time ./main bitwise
real    0m2.275s
user    0m2.248s

$ time ./main case
real    0m1.161s
user    0m1.124s

$ time ./main lookup
real    0m0.826s
user    0m0.792s

$ time ./main search
real    0m1.086s
user    0m1.060s

(значения для sys, равные 0m0.000s, я убрал)

P.S. Посмотрел ещё раз на времена -- для варианта bitwise оптимизация дала более, чем 2-кратный выйгрыш, для остальных -- заметно меньше

[AestheteAnimus]

Если в распоряжении всего1 КБ, я не вижу смысла использовать компилятор C, а не Ассемблер. И в этом случае, скорее всего, наиболее оптимальным вариантом будет простой сдвиг с определением переноса (если процессор не имеет инструкции определения номера младшего/старшего бита). И думать о переносимости кода на разные платформы я смысла не вижу.

Смысл писать на Си есть. Яркий пример - это AVR архитектура, даже в ней важна переносимость. В то же время RISC машина почти наверняка не будет иметь инструкции определения старшего бита.

А вот фрагмент кода файла main.c:

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

        if (strcmp(argv[1], "case") == 0)
            method = bit_index_case;
        else if ( strcmp(argv[1], "lookup") == 0)
            method = bit_index_case;

Ну что тут скажешь... дятел... Посыпаю голову пеплом...
Поправил, теперь имею такие вот результаты (оптимизация 3):

Код:

stub real 0m0.478s user 0m0.475s sys 0m0.003s bitwise real 0m1.145s user 0m1.136s sys 0m0.000s case real 0m0.862s user 0m0.856s sys 0m0.000s lookup real 0m0.713s user 0m0.708s sys 0m0.000s search real 0m0.614s user 0m0.606s sys 0m0.007s

странно, в man gcc описываются уровни только до O3. Хотя интереса ради проверил, он и O8 скушал, не ругнулся
но вообще такого рода тесты правильно было бы компилировать с O0, иначе не факт, что в бинарник попадут ваши ухищрения, а не компиляторные...

И в самом деле нет O4 Тем не менее, категорически не согласен, что компилить надо с О0. То, что компилятор оптимизирует предусматривается хотябы тем фактом, что стандарт определяет квалификатор volatile. Так что все мои "ухищрения" должны ожидаемо оптимизироваться (что и происходит), если не сказано иначе.

[whirlwind]

И в самом деле нет O4 Тем не менее, категорически не согласен, что компилить надо с О0. То, что компилятор оптимизирует предусматривается хотябы тем фактом, что стандарт определяет квалификатор volatile. Так что все мои "ухищрения" должны ожидаемо оптимизироваться (что и происходит), если не сказано иначе.

если gcc запустить без указания уровня оптимизации, он будет использовать O2, умолчание у него такое
но речь не о том. То, чем мы занимаемся -- это вроде интеллектуальной игры. Вряд ли в реальной системе прийдется выжимать такие крошки. Умные книги учат, что в таком случае надо перепроектировать систему целиком, чтобы устранить узкие места как таковые. А если уж попали в совсем экстремальные условия, то тогда уж забить на переносимость и перейти на ассемблер. Архитектур, в конце концов, не так уж и много, а в рамках конкретной организации врядли больше трех наберется.
Так вот, для того чтобы обеспечить чистоту эксперимента, оптимизацию нужно отключать. Потому что точно не известно, как себя проявит компилятор в каждом конкретном случае.

[AestheteAnimus]

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

Именно, это просто интеллектуальная игра, целью который является сделать красивый алгоритм. Согласитесь же, бинарный поиск достаточно красив Хотя с точки зрения ассемблера не очень эффеткивен и в нем (без оптимизации) приходится многократно перезагружать переменные из памяти в регистры - исправление именно этого обстоятельства я впервую очередь жду от оптимизации. Увы, х86 ассемблер знаю не особо хорошо, а в AT синтаксисе вообще плаваю, так что не могу проследить всех нюансов конечного кода. Но, к слову об архитектурах, ниже листинг для AVR. Набор комманд этой архитектуры мне куда ближе... Можно конечно соптимизировать под 8-битность, но мне было лень.

Без оптимизации:

Код:

ssize_t bit_index_search(uint8_t x) { d2: cf 93 push r28 d4: df 93 push r29 d6: cd b7 in r28, 0x3d ; 61 d8: de b7 in r29, 0x3e ; 62 da: 25 97 sbiw r28, 0x05 ; 5 dc: 0f b6 in r0, 0x3f ; 63 de: f8 94 cli e0: de bf out 0x3e, r29 ; 62 e2: 0f be out 0x3f, r0 ; 63 e4: cd bf out 0x3d, r28 ; 61 e6: 8b 83 std Y+3, r24 ; 0x03 if (x == 0) return -1; e8: 8b 81 ldd r24, Y+3 ; 0x03 ea: 88 23 and r24, r24 ec: 29 f4 brne .+10 ; 0xf8 <bit_index_search+0x26> ee: 8f ef ldi r24, 0xFF ; 255 f0: 9f ef ldi r25, 0xFF ; 255 f2: 9d 83 std Y+5, r25 ; 0x05 f4: 8c 83 std Y+4, r24 ; 0x04 f6: 26 c0 rjmp .+76 ; 0x144 <bit_index_search+0x72> ssize_t n = 0; f8: 1a 82 std Y+2, r1 ; 0x02 fa: 19 82 std Y+1, r1 ; 0x01 if (x > 0xF) {n += 4; x >>= 4; } fc: 8b 81 ldd r24, Y+3 ; 0x03 fe: 80 31 cpi r24, 0x10 ; 16 100: 48 f0 brcs .+18 ; 0x114 <bit_index_search+0x42> 102: 89 81 ldd r24, Y+1 ; 0x01 104: 9a 81 ldd r25, Y+2 ; 0x02 106: 04 96 adiw r24, 0x04 ; 4 108: 9a 83 std Y+2, r25 ; 0x02 10a: 89 83 std Y+1, r24 ; 0x01 10c: 8b 81 ldd r24, Y+3 ; 0x03 10e: 82 95 swap r24 110: 8f 70 andi r24, 0x0F ; 15 112: 8b 83 std Y+3, r24 ; 0x03 if (x > 0x3) {n += 2; x >>= 2; } 114: 8b 81 ldd r24, Y+3 ; 0x03 116: 84 30 cpi r24, 0x04 ; 4 118: 48 f0 brcs .+18 ; 0x12c <bit_index_search+0x5a> 11a: 89 81 ldd r24, Y+1 ; 0x01 11c: 9a 81 ldd r25, Y+2 ; 0x02 11e: 02 96 adiw r24, 0x02 ; 2 120: 9a 83 std Y+2, r25 ; 0x02 122: 89 83 std Y+1, r24 ; 0x01 124: 8b 81 ldd r24, Y+3 ; 0x03 126: 86 95 lsr r24 128: 86 95 lsr r24 12a: 8b 83 std Y+3, r24 ; 0x03 if (x > 0x1) {n += 1;} 12c: 8b 81 ldd r24, Y+3 ; 0x03 12e: 82 30 cpi r24, 0x02 ; 2 130: 28 f0 brcs .+10 ; 0x13c <bit_index_search+0x6a> 132: 89 81 ldd r24, Y+1 ; 0x01 134: 9a 81 ldd r25, Y+2 ; 0x02 136: 01 96 adiw r24, 0x01 ; 1 138: 9a 83 std Y+2, r25 ; 0x02 13a: 89 83 std Y+1, r24 ; 0x01 return n; 13c: 89 81 ldd r24, Y+1 ; 0x01 13e: 9a 81 ldd r25, Y+2 ; 0x02 140: 9d 83 std Y+5, r25 ; 0x05 142: 8c 83 std Y+4, r24 ; 0x04 144: 8c 81 ldd r24, Y+4 ; 0x04 146: 9d 81 ldd r25, Y+5 ; 0x05 148: 25 96 adiw r28, 0x05 ; 5 14a: 0f b6 in r0, 0x3f ; 63 14c: f8 94 cli 14e: de bf out 0x3e, r29 ; 62 150: 0f be out 0x3f, r0 ; 63 152: cd bf out 0x3d, r28 ; 61 154: df 91 pop r29 156: cf 91 pop r28 158: 08 95 ret

С оптимизацией (Os):

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

ssize_t bit_index_search(uint8_t x)
{
  a8:    28 2f           mov    r18, r24
    if (x == 0)  return -1;
  aa:    88 23           and    r24, r24
  ac:    19 f4           brne    .+6    ; 0xb4 <bit_index_search+0xc>
  ae:    8f ef           ldi    r24, 0xFF; 255
  b0:    9f ef           ldi    r25, 0xFF; 255
  b2:    08 95           ret

    ssize_t n = 0;
    if (x > 0xF)  {n += 4; x >>= 4; }
  b4:    80 31           cpi    r24, 0x10; 16
  b6:    18 f4           brcc    .+6    ; 0xbe <bit_index_search+0x16>
  b8:    80 e0           ldi    r24, 0x00; 0
  ba:    90 e0           ldi    r25, 0x00; 0
  bc:    04 c0           rjmp    .+8    ; 0xc6 <bit_index_search+0x1e>
  be:    22 95           swap    r18
  c0:    2f 70           andi    r18, 0x0F; 15
  c2:    84 e0           ldi    r24, 0x04; 4
  c4:    90 e0           ldi    r25, 0x00; 0
    if (x > 0x3)  {n += 2; x >>= 2; }
  c6:    24 30           cpi    r18, 0x04; 4
  c8:    18 f0           brcs    .+6    ; 0xd0 <bit_index_search+0x28>
  ca:    02 96           adiw    r24, 0x02; 2
  cc:    26 95           lsr    r18
  ce:    26 95           lsr    r18
    if (x > 0x1)  {n += 1;}
  d0:    22 30           cpi    r18, 0x02; 2
  d2:    08 f0           brcs    .+2    ; 0xd6 <bit_index_search+0x2e>
  d4:    01 96           adiw    r24, 0x01; 1

    return n;
}
  d6:    08 95           ret

[Grom]

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

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

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

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

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

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

Полностью согласен, моё упущение.