Re: Быстро проверить на BCD - Алгоритмы

Быстро проверить на BCD

	От:	tyomchick
	Дата:	26.06.17 14:17
	Оценка:

Есть ли какой то быстрый способ проверить, что целое число в шестнадцатеричном представлении содержит только десятичные цифры?

Даже самую простую задачу можно сделать невыполнимой, если провести достаточное количество совещаний

Re: Быстро проверить на BCD

	От:	Слава
	Дата:	26.06.17 14:24
	Оценка:	+1

Здравствуйте, tyomchick, Вы писали:

T>Есть ли какой то быстрый способ проверить, что целое число в шестнадцатеричном представлении содержит только десятичные цифры?

Есть. Двигать вправо, читать по 4 битика и проверять — не больше ли они, чем 9.

Re[2]: Быстро проверить на BCD

	От:	tyomchick
	Дата:	26.06.17 14:28
	Оценка:

Здравствуйте, Слава, Вы писали:

С>Здравствуйте, tyomchick, Вы писали:

T>>Есть ли какой то быстрый способ проверить, что целое число в шестнадцатеричном представлении содержит только десятичные цифры?

С>Есть. Двигать вправо, читать по 4 битика и проверять — не больше ли они, чем 9.

Ну это "в лоб", я думал может какая битовая магия есть.

Даже самую простую задачу можно сделать невыполнимой, если провести достаточное количество совещаний

Re[3]: Быстро проверить на BCD

	От:	watchmaker
	Дата:	26.06.17 15:20
	Оценка:	2 (1)

Здравствуйте, tyomchick, Вы писали:

С>>Есть. Двигать вправо, читать по 4 битика и проверять — не больше ли они, чем 9.

T>Ну это "в лоб", я думал может какая битовая магия есть.

Типа такой, что ли?

bool is_bcd(ui32 x) { 
    return 0 == ((((x >> 1) & 0x77777777) + 0x33333333) & 0x88888888);
}

Неужели этот код настолько часто исполняется, что стоит заморачиваться с подобными оптимизациями? :)

Re: Быстро проверить на BCD

	От:	Alexander G
	Дата:	26.06.17 15:25
	Оценка:

Наверное как-то так?

bool IsBCD(uint32_t val)
{
  uint32_t possible_non_bcd = val & 0x88888888; // 8,9,A,B,C,D,E,F
  
  if ( (possible_non_bcd >> 1) & val )
    return false; // C, D, E, F


  if ( (possible_non_bcd >> 2) & val )
    return false; // A, B

  return true;
}

Русский военный корабль идёт ко дну!

Re[4]: Быстро проверить на BCD

	От:	tyomchick
	Дата:	27.06.17 07:12
	Оценка:

Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, tyomchick, Вы писали:

С>>>Есть. Двигать вправо, читать по 4 битика и проверять — не больше ли они, чем 9.

T>>Ну это "в лоб", я думал может какая битовая магия есть.

W>Типа такой, что ли?

bool is_bcd(ui32 x) { 
W>    return 0 == ((((x >> 1) & 0x77777777) + 0x33333333) & 0x88888888);
W>}
W>

Спасибо

W>Неужели этот код настолько часто исполняется, что стоит заморачиваться с подобными оптимизациями?

Ну не то, что бы я заморачивался. Просто вот так же и короче и чуть быстрее работает (проверил).
Полезно в библиотеке функцию иметь.

Даже самую простую задачу можно сделать невыполнимой, если провести достаточное количество совещаний

Re[2]: Быстро проверить на BCD

	От:	tyomchick
	Дата:	27.06.17 07:35
	Оценка:

Здравствуйте, Alexander G, Вы писали:

AG>Наверное как-то так?

AG>

AG>bool IsBCD(uint32_t val)
AG>{
AG>  uint32_t possible_non_bcd = val & 0x88888888; // 8,9,A,B,C,D,E,F
  
AG>  if ( (possible_non_bcd >> 1) & val )
AG>    return false; // C, D, E, F


AG>  if ( (possible_non_bcd >> 2) & val )
AG>    return false; // A, B

AG>  return true;
AG>}
AG>

Выглядит хорошо, но работает сильно медленнее простой проверки тетрад.

Даже самую простую задачу можно сделать невыполнимой, если провести достаточное количество совещаний

Re[3]: Быстро проверить на BCD

	От:	watchmaker
	Дата:	27.06.17 10:15
	Оценка:

Здравствуйте, tyomchick, Вы писали:
T>Здравствуйте, Alexander G, Вы писали:

AG>>  if ( (possible_non_bcd >> 2) & val )
AG>>    return false; // A, B
AG>>

T>Выглядит хорошо, но работает сильно медленнее простой проверки тетрад.

А как проверял? А то может тут просто компилятор недостаточно умный и у него не получилось свернуть три return в один. Из-за этого, например, остались условные переходы, которые из-за особенностей тестовых данных могут плохо предсказываться. Не то чтобы от такого объяснения решение стразу стало лучше, но интересно, если немного помочь компилятору и чуть-чуть переписать вышеприведённый код в таком виде, то что-нибудь существенно изменится?

bool is_bcd(ui32 x) {
      return !(((x >> 1) & 0x44444444) & (x | (x << 1)));
}

Ну кроме уменьшения понятности :)

Re[4]: Быстро проверить на BCD

	От:	tyomchick
	Дата:	27.06.17 12:34
	Оценка:

Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, tyomchick, Вы писали:
T>>Здравствуйте, Alexander G, Вы писали:
W>

AG>>>  if ( (possible_non_bcd >> 2) & val )
AG>>>    return false; // A, B
AG>>>

T>>Выглядит хорошо, но работает сильно медленнее простой проверки тетрад.

W>А как проверял? А то может тут просто компилятор недостаточно умный и у него не получилось свернуть три return в один. Из-за этого, например, остались условные переходы, которые из-за особенностей тестовых данных могут плохо предсказываться. Не то чтобы от такого объяснения решение стразу стало лучше, но интересно, если немного помочь компилятору и чуть-чуть переписать вышеприведённый код в таком виде, то что-нибудь существенно изменится?

Проверял я на С#

.
Просто проверка чисел от 0 до 10^9

W>

W>bool is_bcd(ui32 x) {
W>      return !(((x >> 1) & 0x44444444) & (x | (x << 1)));
W>}

Ну кроме уменьшения понятности

Да, так лучше. Производительность приблизительно на уровне такого:

    private static bool IsBCD(uint value)
    {
        return !(((value & 0xF) > 0x09) 
            ||  ((value & 0xF0) > 0x90)
            ||  ((value & 0xF00) > 0x900)
            ||  ((value & 0xF000) > 0x9000)
            ||  ((value & 0xF0000) > 0x90000)
            ||  ((value & 0xF00000) > 0x900000)
            ||  ((value & 0xF000000) > 0x9000000)
            ||  ((value & 0xF0000000) > 0x90000000));
    }

Но твой первый вариант всё равно быстрее.

Даже самую простую задачу можно сделать невыполнимой, если провести достаточное количество совещаний

Re[5]: Быстро проверить на BCD

От:	rameel	https://github.com/rsdn/CodeJam
Дата:	27.06.17 16:30
Оценка:

Здравствуйте, tyomchick, Вы писали:

T>Проверял я на С#

.

Текущий JIT не достаточно прозорлив в отличие от компиляторов C++, которые умеют вот такое:

bool is_bcd1(unsigned int val)
{
  unsigned int possible_non_bcd = val & 0x88888888; // 8,9,A,B,C,D,E,F
  
  if ((possible_non_bcd >> 1) & val)
    return false; // C, D, E, F


  if ((possible_non_bcd >> 2) & val)
    return false; // A, B

  return true;
}

превратить вот в такое:

bool is_bcd3(unsigned int val)
{
  unsigned int possible_non_bcd = val & 0x88888888; // 8,9,A,B,C,D,E,F
  
  return (((possible_non_bcd >> 1) | (possible_non_bcd >> 2)) & val) == 0;
}

и сгенерировать одинаковый код. Вот пруф: https://godbolt.org/g/KJ8XLo

Для джита же эту оптимизацию нужно провести вручную.

public static bool is_bcd2(uint val)
{
    uint possible_non_bcd = val & 0x88888888; // 8,9,A,B,C,D,E,F

    return (((possible_non_bcd >> 1) | (possible_non_bcd >> 2)) & val) == 0;
}

Пруф: SharpLab

; C++
mov     eax, edi
and     eax, -2004318072
mov     edx, eax
shr     eax, 2
shr     edx
or      eax, edx
test    eax, edi
sete    al
ret

; JIT x86
mov   edx, ecx
and   edx, 0x88888888
mov   eax, edx
shr   eax, 1
shr   edx, 0x2
or    eax, edx
and   eax, ecx
setz  al
movzx eax, al
ret

... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

Отредактировано 27.06.2017 16:35 rameel . Предыдущая версия .

Переместить
Удалить
Выделить ветку

Пока на собственное сообщение не было ответов, его можно удалить.

Заголовок: