Придумалось.

[Караидель]

Задачка программерам: написать функцию принимающую число (байт), значение бита и номер бита и возвращающую, соответственно, число с изменённым битом. Функция должна быть максимально оптимизирована. А потом можно написать вариант (опять-таки, максимально оптимизированный) для 32-битного числа. Интересно, кто-то придумает решение оптимальнее моего?

@темы: Программизм

Comments

[баянолог]

оптимизированный по скорости:

dword setbit(dword var, int bit, int bitval)

{

static dword truebit(1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648);



static dword falsebit(4294967294, 4294967293, 4294967291, 4294967287, 4294967279, 4294967263, 4294967231, 4294967167, 4294967039, 4294966783, 4294966271, 4294965247, 4294963199, 4294959103, 4294950911, 4294934527, 4294901759, 4294836223, 4294705151, 4294443007, 4293918719, 4292870143, 4290772991, 4286578687, 4278190079, 4261412863, 4227858431, 4160749567, 4026531839, 3758096383, 3221225471, 2147483647);



if(bitval)return var|truebit[bit]; else return var&falsebit[bit];

}

[баянолог]

или надо вместо static писать const? вощем чтоб при каждом вызове массивы не инициализировались.

[Караидель]

баянолог

А чтоб был компромис между скоростью и потребляемой памятью?

[баянолог]

return ((0xFFFFFFFF - 2<<bit) & val ) * ((bitval + 1) % 2) + ((2<<bit) | val ) * bitval;



но это в разы медленнее будет.

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

[Караидель]

баянолог

Только что ещё решение придумала:

dword setbit(dword var,int bit,int shift)

{

if(bit) return var|(1<<shift);

else return var&~(1<<shift);

}



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

[Aaz]

Мнэ... а к языкам и платформам требования выдвигаются?

Потому что самый оптимальный - это такой:



procedure BitSet(var Buf; ix:integer);

asm

bts [eax],edx

end;

[Караидель]

Aaz

Це хто? Не знаю такой язык...

[Aaz]

Караидель

Ассемблер. В обрамлении Паскаля.

Можно и в Си обрамить, но я там в параметрах путаюсь.)))



Инструкция bts (bit test and set) меняет заданный бит по заданному адресу. Причём номер бита может быть произвольным.

[Караидель]

Aaz

Ты уверен? Это с какого проца добавили такую команду?

[Караидель]

Aaz

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

[Aaz]

Караидель

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



http://www.thepicklepages.com/main/.../instr/bts.html

- здесь говорят, что с 386+. Склонен верить. :-)



Единственное что, я немножко неправильно понял задачу. bts устанавливает заданный бит в единицу. Меняет текущее значение инструкция btc. :-)

[Aaz]

Караидель

во-вторых относится к очень медленным командам.

Это да. Зато меняет произвольный бит от заданного места до пока память не закончится. :-)



Ладно, я ещё подумаю.

[Караидель]

Aaz

http://www.kolasc.net.ru/cdo/progra...embler/bts.html Он устанавливает его всегда в единицу, что не соответствует условиям задачи.