Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 01:12

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 65 ]  На страницу Пред.  1, 2, 3, 4, 5  След.
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 01, 2006 19:30 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Не, не так, 32 сравнения!
Нужно (ассемблер)
; предположим, число в еах
cmp eax, 0
jne begin
jmp exit_no_bit
begin :
and eax, 1111111111111110000000000000000
jz l_0_15
and eax , 11111111000000000000000000000000
jz l_16_23
and eax, 11110000000000000000000000000000
jz l_24_27
and eax , 11000000000000000000000000000000
jz l_28_29
and eax , 10000000000000000000000000000000
jz l_bit30
mov eax , 31
jmp exit
l_bit30 :
mov eax , 30
jmp exit
l_28_29 :
and eax , 00100000000000000000000000000000
jz l_bit28
mov eax , 29
jmp exit
l_bit28 :
mov eax , 28
jmp exit
l_24_27 :
and eax , 00001100000000000000000000000000
jz l_24_25
and eax , 00001000000000000000000000000000
jz l_bit26 :
mov eax , 27
jmp exit
l_bit26 :
mov eax , 26
jmp exit
l_24_25 :

И Т.Д. - дерево - в любом случае не более
5 сравнений

Извиняюсь, ошибся cо степенями в десятичном выражении, поправил


Последний раз редактировалось вопрос Пт сен 01, 2006 20:37, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 01, 2006 19:48 
Не в сети

Зарегистрирован: Ср май 03, 2006 11:27
Сообщения: 1394
Откуда: St.Petersburg
Благодарил (а): 2 раз.
Поблагодарили: 11 раз.
вроде посылал куда-то пропало

Код:

: BREAK POSTPONE EXIT POSTPONE THEN ; IMMEDIATE

: MAX-BIT
  DUP 0xFFFF0000 AND DUP IF NIP ELSE DROP THEN
DUP 0xFF00FF00 AND DUP IF NIP ELSE DROP THEN
DUP 0xF0F0F0F0 AND DUP IF NIP ELSE DROP THEN
DUP 0xCCCCCCCC AND DUP IF NIP ELSE DROP THEN
DUP 0xAAAAAAAA AND DUP IF NIP BREAK DROP  ;

: MAX-BIT-STAP
OVER AND DUP IF NIP BREAK DROP  ;

: MAX-BIT
0xFFFF0000 MAX-BIT-STAP
0xFF00FF00 MAX-BIT-STAP
0xF0F0F0F0 MAX-BIT-STAP
0xCCCCCCCC MAX-BIT-STAP
0xAAAAAAAA MAX-BIT-STAP ;


: UNDER+  ROT + SWAP ;

: LOG2_1                        ( n -- log2 )
      -1 SWAP                       ( log2 n)
      DUP 0xFFFF0000 AND IF   16  UNDER+  16 RSHIFT   THEN
      DUP 0x0000FF00 AND IF    8  UNDER+   8 RSHIFT   THEN
      DUP 0x000000F0 AND IF    4  UNDER+   4 RSHIFT   THEN
      DUP 0x0000000C AND IF    2  UNDER+   2 RSHIFT   THEN
      DUP 0x00000002 AND IF    1  UNDER+   1 RSHIFT   THEN
      1 AND +   ( log2)
;



Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 01, 2006 21:04 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Нет, нет, все не так! :)

Код:
generic WIDTH = 32;

signal x : std_logic_vector(WIDTH - 1 downto 0);
signal max_bit : integer range to to WIDTH;

for i in WIDTH-1 downto 0 generate
begin
   if x(i) = '1' and conv_integer('0' & x(WIDTH-1 downto i)) = 0 then max_bit <= i; end if;
end


:P


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 01, 2006 21:42 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Цитата:
Нет, нет, все не так!

Неужели всё?

_________________
понимаю некоторую бестолковость некоторых вопросов


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 01, 2006 21:58 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
вопрос писал(а):
Неужели всё?


Даже включая приведенный мной код! :))

Думается, сдвигом будет все-таки удобнее.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 02, 2006 00:39 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Хм. Моё сообщение никто не прочёл ... :(

_________________
понимаю некоторую бестолковость некоторых вопросов


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 02, 2006 00:42 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Такой алгоритм будет действительно быстрее "в среднем", но я говорил про удобство. Удобство в данном случае определяется и наглядностью тоже.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 02, 2006 01:36 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Хищник писал(а):
Думается, сдвигом будет все-таки удобнее.


я тоже ничего более подходящего не нашел 8(
а так хотелось получить математическое решение!


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 02, 2006 06:11 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Самый простой вариант у меня выглядит так:
Код:
: MSB ( n --> MSB ) 
           0 BEGIN SWAP DUP WHILE
                          2/ SWAP 1+
           REPEAT 1+ SWAP 1- LSHIFT ;

но время работы такого алгоритма будет различно для различных чисел 8(
Впрочем, как и для других предложенных вариантов 8(
Надеюсь найдется математик, который скажет, что все далается с помощью трех арифметических и двух логических операций 8)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 02, 2006 07:50 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Но это все оказалось не по делу 8)
Нужно мне было вот что:

Код:
: N>P ( N --> p )
          DUP
          1 BEGIN OVER WHILE
                         10 * SWAP 10 / SWAP
             REPEAT +
           -1 SWAP U/ * ;
и тогда

123 N>P выдаст очень полезное число, которое вместе с двойной арифметикой можно использовать для чисел с фиксированной точкой 8)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 02, 2006 08:28 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
oleg писал(а):
Самый простой вариант у меня выглядит так:
Код:
: MSB ( n --> MSB ) 
           0 BEGIN SWAP DUP WHILE
                          2/ SWAP 1+
           REPEAT 1+ SWAP 1- LSHIFT ;

но время работы такого алгоритма будет различно для различных чисел 8(
Впрочем, как и для других предложенных вариантов 8(
Надеюсь найдется математик, который скажет, что все далается с помощью трех арифметических и двух логических операций 8)


Хм, смотри тогда всё-таки мой алгоритм. Есть предел, этот алгоритм не предельный, но среди сравнений - самый быстрый, т.е. если ты собираешься тестировать все 32 бита и т.д., но можешь тестировать их группами, то экономнее всегго разбить биты пополам, потом снова пополам - по Шеннону, быстрее не будет, но можна создать таблицу готовых решений ...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 02, 2006 08:54 
Не в сети
Аватара пользователя

Зарегистрирован: Пт май 05, 2006 06:19
Сообщения: 192
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
можно выделить 2^32 байт памяти и заполнить их так чтобы
начало_выделеной_облости анализируемое_чисоло + @
давало искомы результат , это самое быстрое решение :)
наверно

_________________
SPF


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 02, 2006 09:52 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
oleg писал(а):
Надеюсь найдется математик, который скажет, что все далается с помощью трех арифметических и двух логических операций Cool


Это, если "логарифмирование" за арифметическую, а "выделение целого" за логическую операции посчитать :))
"Номер старшего единичного бита X" равен "Целое от двоичного логарифма от X" (считать от нуля)

проверяем X=2=0010b старший единичный бит номер 1 (нулевой бит рвен нулю) "Целое от двоичного логарифма от X" равно 1. ok :)

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 02, 2006 12:26 
Не в сети

Зарегистрирован: Ср май 03, 2006 11:27
Сообщения: 1394
Откуда: St.Petersburg
Благодарил (а): 2 раз.
Поблагодарили: 11 раз.
В моем варианте можно избавится от ELSE

Код:
: BREAK POSTPONE EXIT POSTPONE THEN ; IMMEDIATE

: MAX-BIT
DUP 0xFFFF0000 AND DUP IF NIP DUP THEN DROP
DUP 0xFF00FF00 AND DUP IF NIP DUP THEN DROP
DUP 0xF0F0F0F0 AND DUP IF NIP DUP THEN DROP
DUP 0xCCCCCCCC AND DUP IF NIP DUP THEN DROP
DUP 0xAAAAAAAA AND DUP IF NIP BREAK DROP  ;


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 02, 2006 12:35 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
есть у меня подозрение, что странный код:
Код:
IF NIP DUP THEN DROP

везде можно заменить на
Код:
IF SWAP THEN DROP

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 65 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 8


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB