Могу ли я получить расстояние Хэмминга, вычитая вес Хэмминга двух целых чисел?

Могу ли я получить расстояние Хэмминга между двумя числами, вычитая из них вес Хэмминга?

Мне нужно написать программу на ассемблере, чтобы получить расстояние Хэмминга между двумя десятичными целыми числами. Мне просто было любопытно, можно ли просто вычесть веса Хэмминга указанных целых чисел. Или было бы лучше просто пойти по маршруту инструкции XOR и создать цикл для подсчета?


hamming-distance assembly
person user3525508    schedule 19.03.2015    source источник
comment
Конечно, вы не можете этого сделать — даже если веса Хэмминга одинаковы, это не говорит вам, какие биты установлены. Скажем, если в обоих числах установлен только один бит, они оба имеют вес Хэмминга 1, поэтому вы думаете, что расстояние равно 0. Но это верно только в том случае, если установленный бит находится в том же месте, о котором вам не сообщает вес. Кроме того, чтобы получить веса (при условии, что вы их не знаете), вам нужно будет подсчитать биты для обоих операндов, так почему бы не выполнить операцию xor и не подсчитать биты в результате (один раз).   -  person Jester    schedule 19.03.2015

Ответы (1)


arrow_upward
1
arrow_downward

Я согласен с Шутом, я попробовал метод вычитания, и он дает неправильный ответ. Так что я попробовал понемногу, и это сработало. Вот код, я использовал компилятор EMU8086, просто скопируйте, вставьте и запустите (вводите числа без знака с 5 цифрами или меньше, он полностью прокомментирован, чтобы сделать его более понятным):

.stack 100h
;------------------------------------------
.data
;------------------------------------------
msj1  db 'Enter first number: $'
str1  db 6 ;MAX NUMBER OF CHARACTERS ALLOWED (4).
      db ? ;NUMBER OF CHARACTERS ENTERED BY USER.
      db 6 dup (?) ;CHARACTERS ENTERED BY USER. 
num1  dw ?     
msj2  db 13,10,13,10,'Enter second number: $'
str2  db 6 ;MAX NUMBER OF CHARACTERS ALLOWED (4).
      db ? ;NUMBER OF CHARACTERS ENTERED BY USER.
      db 6 dup (?) ;CHARACTERS ENTERED BY USER. 
num2  dw ?          
total dw ? ;TOTAL OF DIFFERENCES BETWEEN NUM1 AND NUM2.
msj3  db 13,10,13,10,'Hamming distance: $'
str3  db 5 dup('$')
;------------------------------------------
.code          
;INITIALIZE DATA SEGMENT.
  mov  ax, @data
  mov  ds, ax
;------------------------------------------        
;DISPLAY MESSAGE.
  mov  ah, 9
  mov  dx, offset msj1
  int  21h
;CAPTURE NUMBER 1 AS STRING.
  mov  ah, 0Ah
  mov  dx, offset str1
  int  21h
;------------------------------------------        
;DISPLAY MESSAGE.
  mov  ah, 9
  mov  dx, offset msj2
  int  21h
;CAPTURE NUMBER 2 AS STRING.
  mov  ah, 0Ah
  mov  dx, offset str2
  int  21h
;------------------------------------------
;CONVERT CAPTURED NUMBERS (STRINGS) TO REAL NUMBERS.
  mov  si, offset str1 ;PARAMETER FOR STRING2NUMBER.
  call string2number
  mov  num1, bx ;RETURNED VALUE.

  mov  si, offset str2 ;PARAMETER FOR STRING2NUMBER.
  call string2number
  mov  num2, bx ;RETURNED VALUE.
;------------------------------------------
  call distance
;------------------------------------------
;DISPLAY DISTANCE.
  mov  ax, total
  call number2string

  mov  ah, 9
  mov  dx, offset msj3
  int  21h

  mov  ah, 9
  mov  dx, offset str3
  int  21h
;------------------------------------------
;STOP UNTIL USER PRESS ANY KEY.
  mov  ah,7
  int  21h
;------------------------------------------
;FINISH THE PROGRAM PROPERLY.
  mov  ax, 4c00h
  int  21h           
;------------------------------------------
;EXTRACT THE 16 BITS OF BOTH NUM1 AND NUM2,
;AND INCREASE TOTAL WHEN BITS ARE DIFFERENT.
;THE DISTANCE RETURNS IN TOTAL.
proc distance
  mov  cx, 16 ;COUNTER (NUMBERS HAVE 16 BITS).
while: 
;EXTRACT LEAST SIGNIFICANT BIT OF NUM1 (DL)
  mov  dl, 0 ;ASSUME BIT WILL BE 0.
  shr  num1, 1 ;EXTRACT BIT TO CARRY FLAG.
  jnc  bit_num1
  mov  dl, 1 ;EXTRACTED BIT WAS 1.
bit_num1:  
;EXTRACT LEAST SIGNIFICANT BIT OF NUM2 (DL)
  mov  dh, 0 ;ASSUME BIT WILL BE 0.
  shr  num2, 1 ;EXTRACT BIT TO CARRY FLAG.   
  jnc  bit_num2
  mov  dh, 1 ;EXTRACTED BIT WAS 1.
bit_num2:  
;GET DISTANCE.
  cmp  dl, dh
  je   bits_equal
  inc  total ;BITS ARE DIFFERENT.
bits_equal:  
;CHECK IF PROCESS HAS FINISHED.  
  loop while
  ret
endp
;------------------------------------------
;NUMBER TO CONVERT MUST ENTER IN AX.
;ALGORITHM : EXTRACT DIGITS ONE BY ONE, STORE
;THEM IN STACK, THEN EXTRACT THEM IN REVERSE
;ORDER TO CONSTRUCT STRING.
proc number2string
  mov  bx, 10 ;DIGITS ARE EXTRACTED DIVIDING BY 10.
  mov  cx, 0 ;COUNTER FOR EXTRACTED DIGITS.
cycle1:       
  mov  dx, 0 ;NECESSARY TO DIVIDE BY BX.
  div  bx ;DX:AX / 10 = AX:QUOTIENT DX:REMAINDER.
  push dx ;PRESERVE DIGIT EXTRACTED FOR LATER.
  inc  cx ;INCREASE COUNTER FOR EVERY DIGIT EXTRACTED.
  cmp  ax, 0  ;IF NUMBER IS
  jne  cycle1 ;NOT ZERO, LOOP. 
;NOW RETRIEVE PUSHED DIGITS.
  mov  si, offset str3
cycle2:  
  pop  dx        
  add  dl, 48 ;CONVERT DIGIT TO CHARACTER.
  mov  [ si ], dl
  inc  si
  loop cycle2  

  ret
endp  
;------------------------------------------
;CONVERT STRING TO NUMBER IN BX.
;SI MUST ENTER POINTING TO THE STRING.
proc string2number
;MAKE SI TO POINT TO THE LEAST SIGNIFICANT DIGIT.
  inc  si ;POINTS TO THE NUMBER OF CHARACTERS ENTERED.
  mov  cl, [ si ] ;NUMBER OF CHARACTERS ENTERED.                                         
  mov  ch, 0 ;CLEAR CH, NOW CX==CL.
  add  si, cx ;NOW SI POINTS TO LEAST SIGNIFICANT DIGIT.
;CONVERT STRING.
  mov  bx, 0
  mov  bp, 1 ;MULTIPLE OF 10 TO MULTIPLY EVERY DIGIT.
repeat:         
;CONVERT CHARACTER.                    
  mov  al, [ si ] ;CHARACTER TO PROCESS.
  sub  al, 48 ;CONVERT ASCII CHARACTER TO DIGIT.
  mov  ah, 0 ;CLEAR AH, NOW AX==AL.
  mul  bp ;AX*BP = DX:AX.
  add  bx,ax ;ADD RESULT TO BX. 
;INCREASE MULTIPLE OF 10 (1, 10, 100...).
  mov  ax, bp
  mov  bp, 10
  mul  bp ;AX*10 = DX:AX.
  mov  bp, ax ;NEW MULTIPLE OF 10.  
;CHECK IF WE HAVE FINISHED.
  dec  si ;NEXT DIGIT TO PROCESS.
  loop repeat ;COUNTER CX-1, IF NOT ZERO, REPEAT.

  ret 
endp
person Jose Manuel Abarca Rodríguez    schedule 19.03.2015