Задачка::Проверка бита

← →
Dimka Maslov © (2014-10-14 11:07) [0]

Дано: имеется целое число (n). Известно, что в нём установлен только один бит, остальные нули.
Требуется установить номер этого бита (i).

Возможные решения:
1) for (i = 0; n && (n & 1) == 0; n>>=1, i++);
2) i = (int)log2((double)n);
3) тупо через switch

Какие ещё могут быть варианты?

← →
Romkin © (2014-10-14 11:11) [1]

Массив.
Вообще зависит от разрядности этого самого числа.

← →
manaka © (2014-10-14 11:16) [2]

> Известно, что в нём установлен только один бит, остальные
> нули

Значит число есть степень 2
Номер бита=степень+1

← →
Юрий Зотов © (2014-10-14 11:22) [3]

2^x = n

x = Log2(n)

← →
manaka © (2014-10-14 11:23) [4]

i:=1; while n<>1 do begin n=n/2; i=i+1; end;

))))))

← →
MBo © (2014-10-14 11:24) [5]

Ассемблер, BSR/BSF

Бинарный поиск
if (x and $FFFF0000)>0 then Index := Index+16; и т.п.

← →
oldman © (2014-10-14 11:24) [6]

> Юрий Зотов © (14.10.14 11:22) [3]
> x = Log2(n)

x=log2(n)+1

← →
Юрий Зотов © (2014-10-14 11:33) [7]

> oldman © (14.10.14 11:24) [6]

Это зависит от соглашения о нумерации. Если оно не оговорено, то в мире IT биты принято нумеровать, начиная с нуля.

← →
Юрий Зотов © (2014-10-14 11:35) [8]

Кто тег не закрыл?

Теперь закрыт.

← →
Dimka Maslov © (2014-10-14 11:35) [9]

> Romkin © (14.10.14 11:11) [1]

Для 64 бит массив будет ооооооооооочень большим

> Юрий Зотов © (14.10.14 11:22) [3]

Вариант 2 получается

> manaka © (14.10.14 11:23) [4]

Вариант 1 получается

> MBo © (14.10.14 11:24) [5]

чё-то не понял

> oldman © (14.10.14 11:24) [6]

log2(1) = 0, а биты нумеруются от 0 до 31. так что всё правильно

← →
MBo © (2014-10-14 11:35) [10]

незакрытый тег, видимо, я оставил.

Погуглил - без ветвлений есть метод:
var i, x: integer; table: array[0..31] of Integer; begin for i := 0 to 31 do //инициализация, метод de Brujin table[ ( $077CB531 * ( 1 shl i ) ) shr 27 ] := i; x := 1 shl 17; Caption := IntToStr(table[(x * $077CB531) shr 27]);

← →
MBo © (2014-10-14 11:37) [11]

>чё-то не понял
Не понял про ассемблерные команды, или про бинарный поиск?

← →
Dimka Maslov © (2014-10-14 11:39) [12]

Про бинарный поиск

← →
MBo © (2014-10-14 11:46) [13]

r:=0; //индекс единичного бита будет тут if (x and $FFFF0000)>0 then r:=r+16; // бит в старшем слове if (x and $FF00FF00)>0 then r:=r+8; // бит в старшем байте одного из слов if (x and $F0F0F0F0)>0 then r:=r+4; // бит в старшем ниббле одного из байтов if (x and $CCCCCCCC)>0 then r:=r+2; //бит в одно из старших битов ниббла if (x and $AAAAAAAA)>0 then r:=r+1; //бит на нечетном месте $AA = bin10101010

← →
Дмитрий С © (2014-10-14 12:42) [14]

Неужели банальную подсветку так сложно сделать с первого раза? :))

← →
Inovet © (2014-10-14 15:59) [15]

> [14] Дмитрий С © (14.10.14 12:42)

Сделай

← →
Inovet © (2014-10-14 15:59) [16]

> [9] Dimka Maslov © (14.10.14 11:35)
> Для 64 бит массив будет ооооооооооочень большим

64 элемента и будет по условию задачи.

← →
Rouse_ © (2014-10-14 18:05) [17]

Самое быстрое, конечно BSR, если задача на оптимизацию по скорости

← →
MBo © (2014-10-14 18:37) [18]

> Самое быстрое, конечно BSR, если задача на оптимизацию по
> скорости

Не факт. Оно, кажется, конвейеры с панталыку сбивает.
Я 4 метода испытал на старом Athlon - с магическим умножением, бинарный поиск, и BSR дают примерно одно и то же время, а сдвиг числа вправо, пока бит не найдется - втрое большее на таком тесте:
for k := 1 to 100000000 do begin i := 1 shl (k mod 32); l := l + BitIndex(i); end;

← →
Dimka Maslov © (2014-10-14 19:20) [19]

> Самое быстрое, конечно BSR, если задача на оптимизацию по
> скорости

Проблема в том, что на 64 битах злые вредоносные существа не дают прямого доступа к ассемблеру. Вот и приходится извращаться.

← →
Pavia © (2014-10-14 19:21) [20]

> Не факт. Оно, кажется, конвейеры с панталыку сбивает.

Только если на микрокоде сделана.

← →
Rouse_ © (2014-10-14 19:24) [21]

> MBo © (14.10.14 18:37) [18]
> Не факт. Оно, кажется, конвейеры с панталыку сбивает.

uses Windows; function GetIndexBsr(Value: DWORD): Byte; assembler; asm bsr eax, eax end; function GetIndexMBo(Value: DWORD): Byte; begin Result := 0; //индекс единичного бита будет тут if (Value and $FFFF0000) > 0 then Result := Result + 16; // бит в старшем слове if (Value and $FF00FF00) > 0 then Result := Result + 8; // бит в старшем байте одного из слов if (Value and $F0F0F0F0) > 0 then Result := Result + 4; // бит в старшем ниббле одного из байтов if (Value and $CCCCCCCC) > 0 then Result := Result + 2; //бит в одно из старших битов ниббла if (Value and $AAAAAAAA) > 0 then Result := Result + 1; //бит на нечетном месте $AA = bin10101010 end; var I: Integer; S: DWORD; begin Randomize; S := GetTickCount; for I := 0 to 100000000 do GetIndexBsr(I); Writeln(GetTickCount - S); S := GetTickCount; for I := 0 to 100000000 do GetIndexMBo(I); Writeln(GetTickCount - S); Readln; end.

265
1778

← →
Rouse_ © (2014-10-14 19:27) [22]

PS^ тем более что GetIndexMBo(6) = 3.
Или я не тот алгритм взял?

← →
Rouse_ © (2014-10-14 19:28) [23]

> Dimka Maslov © (14.10.14 19:20) [19]
> Проблема в том, что на 64 битах злые вредоносные существа
> не дают прямого доступа к ассемблеру. Вот и приходится извращаться.

Приведенный в [21] код достаточно успешно компилируется и работает в 64 битах :)

← →
Rouse_ © (2014-10-14 19:34) [24]

Может и не в тему, но тоже хочу задачку для разминки мозга подкинуть.
Дан ряд чисел от единицы до N (к примеру если N = 6, то ряд выглядит как 1,2,3,4,5,6).
Задача: написать функцию возвращающую сумму всех чисел ряда. (При N = 6, результат 21)
Ограничения - функция не должна использовать цикл или рекурсию.

← →
Dimka Maslov © (2014-10-14 19:35) [25]

> Приведенный в [21] код достаточно успешно компилируется
> и работает в 64 битах :)

Смотря каких. Маздайный С++ говорит, что
error C4235: nonstandard extension used : "__asm" keyword not supported on this architecture

И всё. Приплыли.

← →
Rouse_ © (2014-10-14 19:38) [26]

Под арму чтоль компилишь?

← →
Rouse_ © (2014-10-14 19:39) [27]

под 64 битами все пахет в MS VC++ 2010

← →
MBo © (2014-10-14 19:39) [28]

> Или я не тот алгритм взял?

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

var i, k, l: Integer; table: array[0..31] of Integer; t: DWord; function BitIndexBSR(Value: Integer): Integer; asm BSR EAX,EAX end; function BitIndexDeBruijn(Value: Integer): Integer; begin Result := table[(Value * $077CB531) shr 27]; end; function BitIndexSHR(Value: Integer): Integer; begin Result :=0; while (Value and 1) = 0 do begin Inc(Result); Value := Value shr 1; end; end; function BitIndexBinS(Value: Integer): Integer; begin result:=0; //индекс единичного бита будет тут if (Value and $FFFF0000)<>0 then result:=result+16; // бит в старшем слове if (Value and $FF00FF00)<>0 then result:=result+8; // бит в старшем байте одного из слов if (Value and $F0F0F0F0)<>0 then result:=result+4; // бит в старшем ниббле одного из байтов if (Value and $CCCCCCCC)<>0 then result:=result+2; //бит в одно из старших битов ниббла if (Value and $AAAAAAAA)<>0 then result:=result+1; //бит на нечетном месте $AA = bin10101010 end; begin l := 0; for i := 0 to 31 do //инициализация, метод de Brujin table[ ( $077CB531 * ( 1 shl i ) ) shr 27 ] := i; t := GetTickCount; for k := 1 to 100000000 do begin i := 1 shl (k mod 32); l := l + BitIndexBSR(i); end; Memo1.Lines.Add(Format("BSR %d", [GetTickCount- t])); t := GetTickCount; for k := 1 to 100000000 do begin i := 1 shl (k mod 32); l := l + BitIndexDeBruijn(i); end; Memo1.Lines.Add(Format("DeBruijn %d", [GetTickCount- t])); t := GetTickCount; for k := 1 to 100000000 do begin i := 1 shl (k mod 32); l := l + BitIndexBinS(i); end; Memo1.Lines.Add(Format("BinSearch %d", [GetTickCount- t])); t := GetTickCount; for k := 1 to 100000000 do begin i := 1 shl (k mod 32); l := l + BitIndexSHR(i); end; Memo1.Lines.Add(Format("SHR %d", [GetTickCount- t]));

Athlon 3500+
BSR 1422 DeBruijn 1578 BinSearch 1438 SHR 6422

Нет x64 под Венду. Не даёт. А если как в спраке сказано, понизить уровень до ворнинга, то говорит, что bsr и eax неизвестные идентификаторы, однако...

А вот магические числа deBruijn для 64 бит:
Table[(uint64_t)(val * 0x022fdd63cc95386dull) >> 58];

> MBo © (14.10.14 19:39) [28]

Ну как я и говорил изначально - BSR самый шустрый по скорости :)

> Dimka Maslov © (14.10.14 19:40) [29]
> Нет x64 под Венду. Не даёт.

Ты че там такое компиляш?
Давай демку архивом, завтра гляну.

> Rouse_ © (14.10.14 19:34) [24]
>
> Может и не в тему, но тоже хочу задачку для разминки мозга
> подкинуть.
> Дан ряд чисел от единицы до N (к примеру если N = 6, то
> ряд выглядит как 1,2,3,4,5,6).
> Задача: написать функцию возвращающую сумму всех чисел ряда.
> (При N = 6, результат 21)
> Ограничения - функция не должна использовать цикл или рекурсию.
>

Result := (((N + 1) * N) shr 1);

#define BIT0 0x01
#define BIT1 0x02
#define BIT2 0x04
#define BIT3 0x08
#define BIT4 0x10
#define BIT5 0x20
#define BIT6 0x40
#define BIT7 0x80

long BitIndex(long N)
{
__asm
{
mov eax, N
bsr eax, eax
}
}

Microsoft Visual Studio 2013 простое консольное приложение 64 бита. Ассемблер более не дозволен.

> Microsoft Visual Studio 2013 простое консольное приложение
> 64 бита. Ассемблер более не дозволен.

Интринсики же есть _BitScanReverse64

А логарифм как, по скорости?

> [24] Rouse_ © (14.10.14 19:34)
> Задача: написать функцию возвращающую сумму всех чисел ряда. При N = 6, результат 21)

Это что ли?
Для нечётных Н*Н/2
для чётных Н*(Н+1)/2

> Дан ряд чисел от единицы до N

https://ru.wikipedia.org/wiki/%C0%F0%E8%F4%EC%E5%F2%E8%F7%E5%F1%EA%E0%FF_%EF%F0%EE%E3%F0%E5%F1%F1%E8%FF#.D0.A1.D1.83.D0.BC.D0.BC.D0.B0_.D0.BF.D0.B5.D1.80.D0.B2.D1.8B.D1.85_.D1.87.D0 .BB.D0.B5.D0.BD.D0.BE.D0.B2_.D0.B0.D1.80.D0.B8.D1.84.D0.BC.D0.B5.D1.82.D0.B8.D1. 87.D0.B5.D1.81.D0.BA.D0.BE.D0.B9_.D0.BF.D1.80.D0.BE.D0.B3.D1.80.D0.B5.D1.81.D1.8 1.D0.B8.D0.B8

?

Есть еще один вариант не методом Гаусса решается, но в принципе - задача решена :)

Задачка::Проверка бита Найти похожие ветки