|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yuri Burger 2:468/85.3 16 Jun 2001 20:21:58
To : Mike Roschin
Subject : вхождение бита при помощи... рахита
--------------------------------------------------------------------------------
14 Jun 01 11:56, Mike Roschin wrote to All:
MR> Джентльмены, можно ли при помощи операций +, -, *, **(степень), /,
MR> \(целочисленное) и %% (по модулю) определить входждение бита N в число X,
Вариант не кривой: нада пользовть and как все нормальные люди
Вариант рахитский:
X - число
N - номер интерисующего нас бита (15-0)
/ - целочисленное деление
^ - возведение в степень
X1=X/(2^(N+1))
X2=X1*(2^(N+1))
X3=(X-X2)/(2^N)
В X3 будет значение нужного бита :)
Объясняю прынцып:
целочисленное деление икса на 2^(N+1) равносильно правому
сдвигу, который уничтожит все биты от 0 до N+1. После этого домножаем на
2^(N+1), устанавливая на свои места оставшиеся биты. Уцелели только те биты,
что стояли слева от нужного нам. Теперь вычтем это число из исходного, чем
уничтожим все биты, что были слева от интерисующего нас. Теперь повторяем
сдвиг на полученном числе, разделив его на 2^N Этим мы уничтожим все биты, что
стоят справа от интерисующего нас, а нужный нам бит передвинется в позицию 0.
Таким образом, результат будет равен либо 0 либо 1, в зависимости от значения
искомого бита.
зы: алгоритм запатентоват и всё такое :))
Kрюгер.
---
* Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
? |
Mike Roschin |
14 Jun 2001 11:56:59 |
 ? |
Sergey Andrianov |
15 Jun 2001 08:46:20 |
|
? |
Vladimir Polyanin |
15 Jun 2001 23:35:36 |
  ? |
Mike Roschin |
19 Jun 2001 15:49:00 |
|
? |
Denis Rojhkov |
15 Jun 2001 23:10:33 |
|
? |
Mike Roschin |
19 Jun 2001 16:32:01 |
|
вхождение бита при помощи... рахита |
Yuri Burger |
16 Jun 2001 20:21:58 |
|
|
