Сейчас на форуме: zds, UniSoft (+5 невидимых)

 eXeL@B —› Программирование —› Обнулить все младшие биты
Посл.ответ Сообщение


Ранг: 218.9 (наставник), 42thx
Активность: 0.16↘0
Статус: Участник
dotnet

 Создано: 10 апреля 2013 22:01
· Личное сообщение · #1

Дано signed int. Условия использовать нельзя. С помощью битовых операций нужно обнулить все биты кроме старшего сдвиги + - / * тоже можно. Уже голову сломал как сделать лучше.

-----
have a nice day


Ранг: 158.5 (ветеран), 219thx
Активность: 0.12↘0.01
Статус: Участник

 Создано: 10 апреля 2013 22:03 · Поправил: ZaZa
· Личное сообщение · #2

Nimnul
AND?
1100 1100 AND 1111 0000 = 1100 0000
1100 0000 AND 1100 0000 = 1100 0000
1100 0000 AND 1000 0000 = 1000 0000
Так сойдет?

Nimnul пишет:
Должен остаться только старший бит.
Чую я, что как минимум без одного сравнения на ноль тут не обойтись...
Перебирать в цикле по "И" от младшего к старшему байту, примерно так, как указано выше...
Затем сравнивать на ноль, и если равно, тогда брать предыдущий результат.
Теоретически - как-то так...

-----
One death is a tragedy, one million is a statistic.


Ранг: 218.9 (наставник), 42thx
Активность: 0.16↘0
Статус: Участник
dotnet

 Создано: 10 апреля 2013 22:05 · Поправил: Nimnul
· Личное сообщение · #3

Должен остаться только старший бит.

1001011 -> 1000000
0010101 -> 0010000

-----
have a nice day


Ранг: 218.9 (наставник), 42thx
Активность: 0.16↘0
Статус: Участник
dotnet

 Создано: 10 апреля 2013 22:08 · Поправил: Nimnul
· Личное сообщение · #4

И вопрос #2

Code:
  1.         int Some(int a, int b, int c, int d)
  2.         {
  3.             if (a > 0)
  4.             {
  5.                 return a;
  6.             }
  7.             else if (b > 0)
  8.             {
  9.                 return b;
  10.             }
  11.             else if (c > 0)
  12.             {
  13.                 return c;
  14.             }
  15.             else
  16.             {
  17.                 return d;
  18.             }
  19.         }


Нужно убрать все условия зная что всегда a > b > c > d

-----
have a nice day

Ранг: 301.4 (мудрец), 194thx
Активность: 0.17↘0.01
Статус: Участник

 Создано: 10 апреля 2013 22:14
· Личное сообщение · #5

не пробовал но как-то так
Code:
  1. mov eax, const
  2. bsr ecx, eax
  3. bts edx, ecx
  4. and eax, edx


Ранг: 218.9 (наставник), 42thx
Активность: 0.16↘0
Статус: Участник
dotnet

 Создано: 10 апреля 2013 22:16 · Поправил: Nimnul
· Личное сообщение · #6

Veliant

к сожалению асм использовать нельзя

-----
have a nice day

Ранг: 301.4 (мудрец), 194thx
Активность: 0.17↘0.01
Статус: Участник

 Создано: 10 апреля 2013 22:20
· Личное сообщение · #7

Nimnul пишет:
bsr использовать нельзя, не везде работает
Под каких динозавров кодите? Они начиная с 386 появились




Ранг: 218.9 (наставник), 42thx
Активность: 0.16↘0
Статус: Участник
dotnet

 Создано: 10 апреля 2013 22:28
· Личное сообщение · #8

Veliant

я в том смысле что асм не везде можно юзать, а так да лучшее решение как всегда на асме

-----
have a nice day


Ранг: 218.9 (наставник), 42thx
Активность: 0.16↘0
Статус: Участник
dotnet

 Создано: 10 апреля 2013 22:36 · Поправил: Nimnul
· Личное сообщение · #9

По первому вопросу нашел довольно оригинальное решение 1 << ( int) log2( x);

-----
have a nice day

Ранг: 301.4 (мудрец), 194thx
Активность: 0.17↘0.01
Статус: Участник

 Создано: 10 апреля 2013 22:42 · Поправил: Veliant
· Личное сообщение · #10

тогда у меня для вас еще оригинальное решение
Code:
  1. GetHiBitMask(val)

Чем не решение? В функции log2 может быть цикл с условиями

| Сообщение посчитали полезным: DimitarSerg, Nimnul


Ранг: 218.9 (наставник), 42thx
Активность: 0.16↘0
Статус: Участник
dotnet

 Создано: 10 апреля 2013 22:53 · Поправил: Nimnul
· Личное сообщение · #11

Code:
  1. int hibit(unsigned int n) {
  2.     n |= (n >>  1);
  3.     n |= (n >>  2);
  4.     n |= (n >>  4);
  5.     n |= (n >>  8);
  6.     n |= (n >> 16);
  7.     return n - (n >> 1);
  8. }


Тоже не плохо но много букв )). Наверно лучшего решения нет

-----
have a nice day

Ранг: 210.5 (наставник), 2thx
Активность: 0.14↘0
Статус: Участник

 Создано: 10 апреля 2013 23:01
· Личное сообщение · #12

Вот хороший материал по теме:

http://graphics.stanford.edu/~seander/bithacks.html

Там есть: Finding integer log base 2 of an integer (aka the position of the highest bit set)

| Сообщение посчитали полезным: Nimnul


Ранг: 218.9 (наставник), 42thx
Активность: 0.16↘0
Статус: Участник
dotnet

 Создано: 11 апреля 2013 00:08 · Поправил: Nimnul
· Личное сообщение · #13

Все таки быстрейшее решение получилось на таблицах спасибо arnix. 100 миллионов операций за ~200 микросекунд. Думаю это близко к практическому потолку, и где то уже не далеко работает от лучшего решения на асме, которое показал Veliant.

А задача #2 все еще актуальна.

-----
have a nice day

Ранг: 15.3 (новичок), 118thx
Активность: 0.01=0.01
Статус: Участник

 Создано: 11 апреля 2013 01:02
· Личное сообщение · #14

Так можно:
Code:
  1. int Same2(int a, int b, int c, int d)
  2. {
  3.     int bits = sizeof(int)*8;
  4.     return (((a >> (bits-1)) & 1) * d) | ((((a >> (bits-1)) & 1) ^ 1) * a);
  5. }


http://ideone.com/acCzxu



Ранг: 53.9 (постоянный), 19thx
Активность: 0.04↘0
Статус: Участник

 Создано: 11 апреля 2013 06:29 · Поправил: Zorn
· Личное сообщение · #15

Nimnul пишет:
зная что всегда a > b > c > d
В чем тогда смысл b и c ?

RaMMicHaeL, а если "a" равно 0 ?




Ранг: 218.9 (наставник), 42thx
Активность: 0.16↘0
Статус: Участник
dotnet

 Создано: 11 апреля 2013 09:56
· Личное сообщение · #16

Zorn

Я забыл сказать что если a == 0 или другое то остальные числа не меньше нуля. Короче говоря задача найти большее из четырех. Как доп. бонус известно что a > b > c > d, но они могут быть равны 0, при этом остальные числа не меньше нуля например a = 0, b = 100, c = 50, d = 10 или a = 0, b = 0, c = 500, d = 100

-----
have a nice day


Ранг: 527.7 (!), 381thx
Активность: 0.16↘0.09
Статус: Участник
Победитель турнира 2010

 Создано: 11 апреля 2013 10:51
· Личное сообщение · #17

Задача #2

Идея найдена на просторах инета.
Проверена, вроде работает.

Code:
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. int Some(int a, int b, int c, int d)
  5. {
  6.          int ab = (a+b+abs(a-b))/2;
  7.          int abc = (ab+c+abs(ab-c))/2;
  8.          return (abc+d+abs(abc-d))/2;
  9. }
  10.  
  11. int main(int argc, char* argv[])
  12. {
  13.          printf("Max from (%d, %d, %d, %d) --> %d\n", 0,0,0,100,Some(0,0,0,100));
  14.          printf("Max from (%d, %d, %d, %d) --> %d\n", 0,0,200,100,Some(0,0,200,100));
  15.          printf("Max from (%d, %d, %d, %d) --> %d\n", 0,300,200,100,Some(0,300,200,100));
  16.          printf("Max from (%d, %d, %d, %d) --> %d\n", 400,300,200,100,Some(400,300,200,100));
  17.          return 0;
  18. }


-----
127.0.0.1, sweet 127.0.0.1

| Сообщение посчитали полезным: Nimnul


Ранг: 218.9 (наставник), 42thx
Активность: 0.16↘0
Статус: Участник
dotnet

 Создано: 11 апреля 2013 11:28
· Личное сообщение · #18

OKOB Работает но медленнее чем на ифах. За пример спасибо.

-----
have a nice day


Ранг: 527.7 (!), 381thx
Активность: 0.16↘0.09
Статус: Участник
Победитель турнира 2010

 Создано: 11 апреля 2013 15:36
· Личное сообщение · #19

Nimnul пишет:
Работает но медленнее чем на ифах.

Даже чисто ассемблерная реализация работает медленнее.

Code:
  1. __declspec(naked) int __cdecl Some(int a, int b, int c, int d)
  2. {
  3.     __asm {
  4. mov eax,[esp+4]
  5. mov edx,[esp+8]
  6. add eax, edx
  7. push eax
  8. sub eax, edx
  9. sub eax, edx
  10. cdq
  11. xor eax, edx
  12. sub eax, edx
  13. pop edx
  14. add eax, edx
  15. shr eax,1
  16. mov edx,[esp+12]
  17. add eax, edx
  18. push eax
  19. sub eax, edx
  20. sub eax, edx
  21. cdq
  22. xor eax, edx
  23. sub eax, edx
  24. pop edx
  25. add eax, edx
  26. shr eax,1
  27. mov edx,[esp+16]
  28. add eax, edx
  29. push eax
  30. sub eax, edx
  31. sub eax, edx
  32. cdq
  33. xor eax, edx
  34. sub eax, edx
  35. pop edx
  36. add eax, edx
  37. shr eax,1
  38. retn
  39.          }
  40. }


-----
127.0.0.1, sweet 127.0.0.1

| Сообщение посчитали полезным: Nimnul
 eXeL@B —› Программирование —› Обнулить все младшие биты
:: Ваш ответ
Жирный  Курсив  Подчеркнутый  Перечеркнутый  {mpf5}  Код  Вставить ссылку 
:s1: :s2: :s3: :s4: :s5: :s6: :s7: :s8: :s9: :s10: :s11: :s12: :s13: :s14: :s15: :s16:


Максимальный размер аттача: 500KB.
Ваш логин: german1505 » Выход » ЛС
   Для печати Для печати