Как я могу узнать, сколько раз 101b отображается в числе? - PullRequest
0 голосов
/ 15 июня 2019

Мне нужно выяснить, сколько раз последовательность 101b показывает 16-битное число. Но мне нужно найти и тех, которые находятся далеко.

Например: в номере 01010101 оно появляется 4 раза. Поскольку 3 являются его частью, а четвертый (если индекс 0 является левым битом) состоит из 3 битов с индексами 1, 4 и 7.

Потому что вы можете относиться к нему как к симметричной последовательности 101b.

Это кажется действительно сложным, но так ли это? Я думаю, что это может быть немного сложно.

Мне удалось узнать, сколько раз он показывает регулярно, например 3, которые вы видите в примере. Но я не знаю, как мне найти симметричные. РЕДАКТИРОВАТЬ: мой учитель имел в виду ротацию, и я неправильно понял проблему, спасибо всем за помощь, хотя

    mov cx,15
Check:

    push dx;the number that I need to check
    and dx,0111b
    cmp dx,101b
    jne Again
Again:

    pop dx
    shr dx,1
    loop check

Ответы [ 4 ]

3 голосов
/ 15 июня 2019

что-то вроде этого (не проверено):

mov dx, yourNumber
mov cx, 16
xor ax, ax
count:
  mov bx, dx
  and bx, 0b111
  cmp bx, 0b101
  jne nope
     inc ax
  nope:
  rol dx, 1
  dec cx
  jnz count

так что в основном вы вращаете регистр 16 раз и на каждой итерации проверяете, равны ли 0b111 младшие 3 бита, маскируя регистр с 0b111. после этого вычисления результат будет в ax, а проверенное вами число должно быть в dx

2 голосов
/ 15 июня 2019

Я не уверен, что понял, где находится 4-я копия.Я (и @sivizius) думал, что он состоит из битов 7, 0 и 1 (переход к верхнему биту).Но, видимо, это не то, что вам нужно.

(Также ваша нумерация битов не имеет смысла. Вы говорите, что старший бит вашего 8-битного числа - это бит 0, но в комментариях вы настаиваете, что хотите работать с 16-битовые числа. Итак, что такое битовое число 1<<15?)

В любом случае, я думаю, вы хотите найти такие шаблоны, как 1.0.1 и 1..0..1?(Где . - это необязательный заполнитель в шаблоне, который может соответствовать 0 или 1).

Вы можете искать тех с чем-то вроде этого (внутри цикла shr dx, 1).

; dumb brute force method.
countloop:                   ; do {
    mov  ax, dx
    and  al, 111b               ; select the bits that matter in 101
    cmp  al, 101b               ; check that it's the pattern we want
    ; do count += ZF somehow

    mov  ax, dx
    and  al, 10101b             ; select the bits that matter in 1.0.1
    cmp  al, 10001b             ; check that it's the pattern we want
    ; do count += ZF somehow

    mov  ax, dx
    and  al, 1001001b           ; select the bits that matter in 1..0..1
    cmp  al, 1000001b           ; check that it's the pattern we want
    ; do count += ZF somehow

   ... for all the rest of the patterns.
   ; Wider patterns will need to use AX instead of AL

    shr  dx, 1
    cmp  dx, 101b
    jae  countloop           ; }while(x >= 0b101);

;;; exit the loop as soon as DX contains no bits high enough to possibly match
;;; with a big loop, this is worth the extra cmp
;;; instead of just using jnz on the  shr dx,1  result

Точно так же, как вы делаете для 101b, за исключением того, что вы устанавливаете биты безразличия в ноль.

Я не думалничего лучше, чем проверка отдельно для каждого возможного шаблона отдельно внутри тела цикла.

"count + = ZF" может быть (386) setz al / add cl, al илипростой jnz более inc cx.(Я думаю, что максимально возможное число меньше 255, так что 8-битный счетчик подойдет.)

Обратите внимание, что я не использую cx в качестве счетчика цикла, вместо этого завершаю цикл после сдвига всехбиты из dx

Другой способ сделать это без ответвлений без SETCC будет

   mov   ax, dx
   and   al, 10101b
   xor   al, 10001b
   sub   al, 1            ; set CF only if AL==0
   adc   cx, 0            ; cx += (al == 0b10001)
2 голосов
/ 15 июня 2019

Логика:

Если вы XOR значение с 1010101010101010b (0xAA), любая 4-битная группа, которая была 0101b станет 1111b, и любая группа, которая не была выиграна 't.

Если вы добавите 1 к 1111b, он переполнится, а если вы добавите 1 к любому другому номеру, он не переполнится.Вы можете организовать это так, чтобы при переполнении сложения это приводило к установке флага переноса.

Вы можете использовать инструкцию adc, чтобы добавить флаг переноса к счету / сумме, чтобы получить общее количество групп, которыепереполнен (количество групп, которые были 0101b изначально).

Это будет только найти 0101b, который выровнен к началу группы.Чтобы он работал для «0101b в любом месте», вам нужно сделать это 4 раза, с поворотом между каждым разом.

Код:

    mov cx,4           ;Number of times to rotate/repeat
    xor ax,ax          ;ax = current sum of 4-bit groups that were 0101b = 0

.nextRotation:
    mov bx,dx          ;bx = the value
    xor bx,0xAAAA      ;dx = any 4-bit group that was 0101b is now 1111b
    add bx,0x1000      ;Carry set if fourth/highest group was originally 0101
    adc ax,0           ;Add carry to the sum
    add bl,0x10        ;Carry set if second group was originally 0101b
    adc ax,0           ;Add carry to the sum
    shl bx,4
    add bx,0x1000      ;Carry set if third group was originally 0101b
    adc ax,0           ;Add carry to the sum
    add bl,0x10        ;Carry set if first/lowest group of 4 bits was originally 0101b
    adc ax,0           ;Add carry to the sum
                       ;ax = number of 4-bit groups that were originally 0101b

    rol dx,1
    loop .nextRotation
1 голос
/ 15 июня 2019

Это кажется действительно сложным, но так ли это?Я думаю, что это может быть немного сложно.

Да, это действительно сложно.Вот как далеко я продвинулся:

Шаг 1. Выполните «кодирование по длине прогона», игнорируя начальные и конечные нули.Примеры (для 8-битных чисел):

01010101 = 1(1s), 1(0s), 1(1s), 1(0s), 1(1s), 1(0s), 1(1s)
11001011 = 2(1s), 2(0s), 1(1s), 1(0s), 2(1s)
11111101 = 6(1s), 1(0s), 1(1s)

Шаг 2: Найти перестановки «пробег единиц, запуск нулей, запуск единиц» и умножить счет каждого цикла.Примеры (для 8-битных чисел):

01010101 = 1(1s), 1(0s), 1(1s), 1(0s), 1(1s), 1(0s), 1(1s)
         = 1     *1     *1
         + 1     *1                   *1
         + 1     *1                                 *1
         + 1                   *1     *1
         + 1                   *1                   *1
         + 1                                 *1     *1
         +               1     *1     *1
         +               1     *1                   *1
         +               1                   *1     *1
         = 1+1+1+1+1+1+1+1 = 9

11001011 = 2(1s), 2(0s), 1(1s), 1(0s), 2(1s)
         = 2     *2     *1
         + 2     *2                   *2
         + 2                   *1     *2
         +               1     *1     *2
         = 4+8+4+2 = 18

11111101 = 6(1s), 1(0s), 1(1s)
         = 6     *1     *1
         = 6

На данный момент;Легко сделать вывод, что эффективная реализация будет включать списки и, вероятно, будет проще реализовать, если используется рекурсия (найдите перестановки, которые включают в себя первый запуск единиц в списке, затем отбросьте первый запуск единиц и первый запуск нулей).и рекурсировать).

...