[NON + URGENTE] Riconoscere palindromicità a livello di bit

[VegetaSSJ5]

Salve ragazzi devo fare un progetto in assembler (MIPS) da consegnare entro la prossima settimana. In pratica data una stringa in ingresso devo vedere se questa è palindroma a livello di bit (es. 1001010000101001) capito? Non mi interessa che mi diciate i comandi (visto che l'assembler mips chi lo conosce?) ma che mi diciate l'algoritmo per risolvere il problema, cioè usare and, or, rotazione a sinistra o destra ecc... Grazie a chi mi risponderà!

[lalli83]

mmm...io ho appena fatto lo stesso esercizio, ma nn in assembler..in C...ti dico come l ho fatto magari ti può aiutare...
Data la stringa "ciao" ovviamente NON palindroma

1° metodo:
mettere in una variabile ausiliaria la stringa --> "oaic"
e poi confrontarla con quella iniziale --> se "oaic" è = a "ciao" è palindroma

2° metodo:
confronto lettera per lettera con due indici, I e J, che partono rispettivamente dall inizio della stringa e dalla fine, fino a quando trovo una coppia diversa --> esempio con "otto"....1° lettera=4° lettera? si...2° lettera=3° lettera? si..allora parola è palindroma!

:D :D

Purtroppo non mi ricordo una mazza di assembler quindi questo è l unio aiuto che ti posso dare, ma penso che il primo metodo sia quello che magari si riesce a realizzare meglio con le operazioni booleane...penso :p :cool: ;)

[VegetaSSJ5]

Originally posted by "lalli83"

mmm...io ho appena fatto lo stesso esercizio, ma nn in assembler..in C...ti dico come l ho fatto magari ti può aiutare...
Data la stringa "ciao" ovviamente NON palindroma

1° metodo:
mettere in una variabile ausiliaria la stringa --> "oaic"
e poi confrontarla con quella iniziale --> se "oaic" è = a "ciao" è palindroma

2° metodo:
confronto lettera per lettera con due indici, I e J, che partono rispettivamente dall inizio della stringa e dalla fine, fino a quando trovo una coppia diversa --> esempio con "otto"....1° lettera=4° lettera? si...2° lettera=3° lettera? si..allora parola è palindroma!

:D :D

Purtroppo non mi ricordo una mazza di assembler quindi questo è l unio aiuto che ti posso dare, ma penso che il primo metodo sia quello che magari si riesce a realizzare meglio con le operazioni booleane...penso :p :cool: ;)

purtroppo il secondo metodo serve per controllare se una parola è palindroma a livello di caratteri e non a livello di bit (infatti ho usato questo metodo per svolgere la prima parte del progetto), ora vedrò se il 1° metodo che mi hai consigliato è attuabile, grazie!

[VegetaSSJ5]

Originally posted by "VegetaSSJ5"



purtroppo il secondo metodo serve per controllare se una parola è palindroma a livello di caratteri e non a livello di bit (infatti ho usato questo metodo per svolgere la prima parte del progetto), ora vedrò se il 1° metodo che mi hai consigliato è attuabile, grazie!

ho appena provato a fare con il primo metodo, ma anche in questo caso non si controlla la palindromicità a livello di bit...

[VegetaSSJ5]

ragazzi proviamo a capovolgere il problema: facciamo conto che io devo trasformare 8 bit di un registro (da 32bit) capovolgendoli, cioè ad esempio se ho in un registro

0110 0001

lo devo trasformare in

1000 0110

(cioè lo devo riscrivere da sinistra verso destra), sapete dirmi come posso fare? posso utilizzare comandi che effettuano operazioni di scalamento, di rotazione e i tradizionali operatori logici....

[cionci]

Ti ho scritto il normale ciclo...

Ho chiamato R1...R8 i registri...

R1 = 0
R2 = 7
R3 = 0
R4 = lunghezza della stringa-1

se lunghezza della stringa è pari allora R5 = lunghezza della stringa / 2 +1
altrimenti R5 = lunghezza della stringa / 2 +2

se R3 uguale R5 vai a [b]successo[/b]
{
se R1 minore di 8
{
R6 = 1
shift a sinistra di R1 posizioni
R7 = stringa[R3] & R6
shift a destra di R1 posizioni
R6 = 1
shift a sinistra di R2 posizioni
R8 = stringa[R4] & R6
shift a destra di R2 posizioni
se R7 diverso da R8 allora vai a [b]insuccesso[/b]
incremento R3
decremento R4
}
R1 = 0
R2 = 7
incremento R3
decremento R4
}

Se invece vuoi invertire un byte puoi fare una cosa simile a quello che succede nel ciclo interno qui sopra... E' praticamente la stessa cosa...

[a2000]

Solo sei righe per me posson bastare :o :o :o
solo sei righe per me voglio dimenticare :o :o :o
capelli biondi da accarezzare :o :o :o
e labbra rosse sulle quali morire. :o :o :o
Solo sei righe per me, solo per me. :o :o :o
Una la voglio perché sa bene ballare. :o :o :o
Una la voglio perché ancor non sa cosa vuol dir l'amore. :o :o :o
Una soltanto perché ha conosciuto tutti tranne me. :o :o :o
Solo sei righe così che dicon' solo di sì :o :o :o :o :o :o



Function f_CarPalindromo(a$)
aa = Asc(a$)
bb = 0
For k = 0 To 7
bb = bb + f_bit(aa, 7 - k) * 2 ^ k
Next k
f_CarPalindromo = Chr$(bb)
End Function



Sub ppp()
a$ = "VegetaSSJ5"
b$ = "¬RÊʆ.¦æ¦j"

ii = Len(a$)
apal$ = ""
For i = ii To 1 Step -1
apal$ = apal$ & f_CarPalindromo(Mid$(a$, i, 1))
Next i

OK = (apal$ = b$)
End Sub



Function f_bit(i8, k)
f_bit = -((i8 And 2 ^ k) > 0)
End Function

[VegetaSSJ5]

Originally posted by "cionci"

Ti ho scritto il normale ciclo...

Ho chiamato R1...R8 i registri...

R1 = 0
R2 = 7
R3 = 0
R4 = lunghezza della stringa-1

se lunghezza della stringa è pari allora R5 = lunghezza della stringa / 2 +1
altrimenti R5 = lunghezza della stringa / 2 +2

se R3 uguale R5 vai a [b]successo[/b]
{
se R1 minore di 8
{
R6 = 1
shift a sinistra di R1 posizioni
R7 = stringa[R3] & R6
shift a destra di R1 posizioni
R6 = 1
shift a sinistra di R2 posizioni
R8 = stringa[R4] & R6
shift a destra di R2 posizioni
se R7 diverso da R8 allora vai a [b]insuccesso[/b]
incremento R3
decremento R4
}
R1 = 0
R2 = 7
incremento R3
decremento R4
}

Se invece vuoi invertire un byte puoi fare una cosa simile a quello che succede nel ciclo interno qui sopra... E' praticamente la stessa cosa...

ragazzi grazie 1000!!!! entro oggi o domani proverò s scrivere il codice in assembler e vi farò sapere quindi se avrò problemi non spariteee!!! :D ;) :cool:

a2000 mi hai scritto un programmino in un linguaggio che non conosco (credo sia c giusto?) per cui è un po' difficile comprenderlo...

[VegetaSSJ5]

Originally posted by "cionci"


Ho chiamato R1...R8 i registri...

R1 = 0
R2 = 7
R3 = 0
R4 = lunghezza della stringa-1

se lunghezza della stringa è pari allora R5 = lunghezza della stringa / 2 +1
altrimenti R5 = lunghezza della stringa / 2 +2

se R3 uguale R5 vai a [b]successo[/b]
{
se R1 minore di 8
{
R6 = 1
shift a sinistra di R1 posizioni
R7 = stringa[R3] & R6
shift a destra di R1 posizioni
R6 = 1
shift a sinistra di R2 posizioni
R8 = stringa[R4] & R6
shift a destra di R2 posizioni
se R7 diverso da R8 allora vai a [b]insuccesso[/b]
incremento R3
decremento R4
}
R1 = 0
R2 = 7
incremento R3
decremento R4
}


cionci tu ad un certo punto dici di shiftare (a sinistra o a destra). ma cosa devo shiftare? se nello shift vengono persi dei bit non fa niente no?

[a2000]

ancora più semplice e commentato ! :)

Sub Pal1()

'Legge la stringa come vettore di numeri binari a 8 bit
Dim a(1 To 10)
a(1) = Asc("V")
a(2) = Asc("e")
a(3) = Asc("g")
a(4) = Asc("e")
a(5) = Asc("t")
a(6) = Asc(".")
a(7) = Asc("¦")
a(8) = Asc("æ")
a(9) = Asc("¦")
a(10) = Asc("j")
ii = UBound(a) 'legge il numero di caratteri della stringa


OK = True 'flag test stringa palindroma.
For i = 1 To Int((ii + 1) / 2) 'Per i=1 alla metà della stringa esegui
ai = a(i) 'carica il carattere i-esimodella stringa nel registro ai
'Calcola b: il carattere palindromo di ai
b = 0 'azzera il registro b
For k = 0 To 7 'Per k = 0 fino a 7 esegui
b = b - ((ai And 2 ^ k) > 0) * 2 ^ (7 - k) 'self-explaining
Next k
If b <> a(ii - i + 1) Then 'se b è diverso dal simmetrico di ai
OK = False 'la stringa non è palindroma
Exit For 'esci dal ciclo
End If
Next i

End Sub

[a2000]

in altre parole:

1) leggi la stringa come numeri a 8 bit
2) per ogni carattere della prima metà della stringa ne determini il palindromo
3) testi se è uguale al simmetrico nella seconda metà della stringa

per determinare il palindromo di un carattere lo spazzoli bit per bit e ne costruisci uno a bit invertiti: 10010111 -> 11101001

[cionci]

R1 = 0
R2 = 7
R3 = 0
R4 = lunghezza della stringa-1

se lunghezza della stringa è pari allora R5 = lunghezza della stringa / 2 +1
altrimenti R5 = lunghezza della stringa / 2 +2

se R3 uguale R5 vai a [b]successo[/b]
{
se R1 minore di 8
{
R6 = 1
shiftare R6 a sinistra di R1 posizioni
R7 = stringa[R3] & R6
shiftare R7 a destra di R1 posizioni
R6 = 1
shiftare R6 a sinistra di R2 posizioni
R8 = stringa[R4] & R6
shiftare R8 a destra di R2 posizioni
se R7 diverso da R8 allora vai a [b]insuccesso[/b]
incremento R3
decremento R4
}
R1 = 0
R2 = 7
incremento R3
decremento R4
}

Uso lo shift invece di moltiplicare e dividere per le potenze di 2...

[VegetaSSJ5]

Originally posted by "a2000"

Sub Pal1()
For k = 0 To 7 'Per k = 0 fino a 7 esegui
b = b - ((ai And 2 ^ k) > 0) * 2 ^ (7 - k) 'self-explaining
Next k
End Sub

puoi spiegarmi cosa significa questo self explaining?

inoltre nell'algoritmo che mi hai dato (il secondo) la lunghezza massima è fino a 10 caratteri mentre invece a me servirebbe fino a max 31 caratteri.

dici anche di caricare il carattere i nel registro a(i) ma non posso fare questo perchè ho a disposizione max 7+8 registri.

[VegetaSSJ5]

a2000 tu hai scritto:
((ai And 2 ^ k) > 0)

cosa vuol dire quel >0???

[a2000]

nell'algoritmo che mi hai dato (il secondo) la lunghezza massima è fino a 10 caratteri mentre invece a me servirebbe fino a max 31 caratteri.
no, no quello è solo un esempio puoi leggere stringhe lunghe a piacere.
intendevo che devi poterle leggere carattere per carattere (caratteri codificati a 8 bit)

dici anche di caricare il carattere i nel registro a(i) ma non posso fare questo perchè ho a disposizione max 7+8 registri.
no, scusa, intendevo dire che puoi caricare, solo per comodità, il carattere i-esimo della stringa, a(i), in un unico registro di appoggio che ho chiamato ai solo per ricordare che ci ho caricato il carattere a(i).

puoi spiegarmi cosa significa questo self explaining?
Giusto, hai ragione.
E' l'operazione che costruisce, un bit alla volta, il carattere palindromo di ai (cioè a(i)) che ho chiamato b.
Per esempio ai = 10001011 --> b = 11010001
Funziona così:

Per ogni bit di ai partendo dal meno significativo
ne leggo il valore con ai And 2^k
vedo se è > 0, ossia se è 1 o 0.
moltiplico il valore del bit trovato (1 o 0) per 2^(7-k)
e lo sommo a b
Ripeti

Tutto questo è fatto con il ciclo:
For k = 0 To 7
b = b - ((ai And 2 ^ k) > 0) * 2 ^ (7 - k)
Next k


Però in assembler:
- l'estrazione del bit k-esimo di ai
- la moltiplicazione per 2^(7-k)
- e la somma ripetuta al registro di calcolo b

può essere realizzata anche molto più facilmente se hai istruzioni del tuo assembler MIPS già predisposte (almeno l'estrazione del bit k-esimo ci dovrebbe essere senza bisogno di fare l'And con 2^k).

[VegetaSSJ5]

Originally posted by "a2000"

Però in assembler:
- l'estrazione del bit k-esimo di ai
- la moltiplicazione per 2^(7-k)
- e la somma ripetuta al registro di calcolo b

può essere realizzata anche molto più facilmente se hai istruzioni del tuo assembler MIPS già predisposte (almeno l'estrazione del bit k-esimo ci dovrebbe essere senza bisogno di fare l'And con 2^k).

grazie sei stato molto gentile, cmq purtroppo non ho a disposizione quel genere di comando che dici tu (il libro riporta tutti i comandi e non ci sono comendi che gestiscono il singolo bit), sarebbe stato molto + facile...

[a2000]

e allora per l'estrazione dei bit devi utilizzare

a AND 1 per il 1° bit
a AND 2 per il 2° bit
a AND 4 per il 3° bit
a AND 8 per il 4° bit
a AND 16 per il 5° bit
a AND 32 per il 6° bit
a AND 64 per il 7° bit
a AND 128 per l' 8° bit

ma è semplice anche così.

[a2000]

tu dirai: grazie al ca++o, non mi potevi scrivere:

a AND 2^k

no, perchè magari è più comodo in assembler "srotolare" un ciclo in pochi passi (8) in otto istruzioni esplicite


c = ai And 1
se c > 0 allora: b = b + 128

c = ai And 2
se c > 0 allora: b = b + 64

c = ai And 4
se c > 0 allora: b = b + 32

c = ai And 8
se c > 0 allora: b = b + 16

c = ai And 16
se c > 0 allora: b = b + 8

c = ai And 32
se c > 0 allora: b = b + 4

c = ai And 64
se c > 0 allora: b = b + 2

c = ai And 128
se c > 0 allora: b = b + 1

[VegetaSSJ5]

ragazzi dopo tante peripezie finalmente ho raggiunto la soluzione! in pratica per costruirmi il palindromo di bit di un carattere memorizzo in 8 registri diversi il bit i-esimo di quel carattere in questo modo:

- per memorizzare il primo bit in un registro faccio lo shift a sinistra di 31 bit in modo tale da avere nel bit + significativo il primo bit; quindi faccio di nuovo lo shift a destra ma questa volta di 24 bit in modo tale che venga memorizzato nella posizione numero 7 (cioè l'ottavo bit) del registro e così da avere alla sua sinistra tutti zeri;

- per memorizzare gli altri devo shiftare a sinistra di 31-i, poi a destra di 31 e di nuovo a sinistra di i.

(rileggendo quello che ho scritto è un casino bestiale!! :eek: :mc: :muro: cmq vi assicuro che è + facile a farsi che a dirsi). cmq alla fine funziona, ho provato la stringa "Fb" e mi dà come risultato che è effettivamente palindroma bit a bit!

grazie a tutti coloro che si sono interessati!!!!

P.S. Domani mattina ho l'esame di Lab. Arch. e per fare questo c@xxo di progetto non ho studiato il resto! Che dio me la mandi buona (mora, alta, con due bette tette e un bel culetto sodo!)! :) :D ;)

[VegetaSSJ5]

vabbè se a qualcuno dovesse servire.... (ma non credo visto che in italia credo che solo noi studiamo l'assembler mips anzichè di un'architettura x86!)
ctrl_bit:
lb $s2, 0($s0) #$s2= il carattere del puntatore a sinistra

#COSTRUZIONE DEL PALINDROMO DI $S2 (metto in $ti il bit i-esimo di $s2)
sll $t0, $s2, 31
srl $t0, $t0, 24

sll $t1, $s2, 30
srl $t1, $t1, 31
sll $t1, $t1, 6

sll $t2, $s2, 29
srl $t2, $t2, 31
sll $t2, $t2, 5

sll $t3, $s2, 28
srl $t3, $t2, 31
sll $t3, $t3, 4

sll $t4, $s2, 27
srl $t4, $t4, 31
sll $t4, $t4, 3

sll $t5, $s2, 26
srl $t5, $t5, 31
sll $t5, $t5, 2

sll $t6, $s2, 25
srl $t6, $t6, 31
sll $t6, $t6, 1

sll $t7, $s2, 24
srl $t7, $t7, 31
sll $t7, $t7, 7

or $s3, $t0, $t1
or $s3, $s3, $t2
or $s3, $s3, $t3
or $s3, $s3, $t4
or $s3, $s3, $t5
or $s3, $s3, $t6
or $s3, $s3, $t7 #in $s3 ho la sequenza palindroma dei bit che compongono il carattere in $s2

lb $s4, 0($s1) #$s4= il carattere del puntatore a destra
bne $s3, $s4, no_pali_bit #se la sequenza di bit che ho costruito è diversa dal carattere del puntatore
#a destra, la stringa non è palindroma bit a bit
addi $s0, $s0, 1 #incremento il puntatore di carattere di sinistra
addi $s1, $s1, -1 #decremento il puntatore di carattere di destra
blt $s1, $s0, pali_bit #se il puntatore di destra si trova a sinistra (ma non lo stesso) del carattere
#puntato dal puntatore di sinistra vuol dire che ho controllato tutti i
#caratteri ed esco dal ciclo
j ctrl_bit #altrimenti itero

[a2000]

Originally posted by "VegetaSSJ5"


...
Che dio me la mandi buona (mora, alta, con due bette tette e un bel culetto sodo!)! :) :D ;)

[/siz]

[VegetaSSJ5]

ragazzi se a qualcuno interessa (ma non credo visto che sono passati 6 mesi :oink: :oink:) a questo esame ho preso 28 :( perchè il prof ha detto che dovevamo gestire anche il caso in cui veniva inserita una stringa come parametro ma in realtà sul testo del problema c'è scritto che era indifferente da linea di comando o da parametro... cmq vabbè.. moderatori non mi bannate per aver "uppato" questo thread vecchio di mesi.:bimbo: :ave::D :D ;)

[recoil]

azz ma dov'ero all'epoca? mi sono perso il MIIIIIPS :eek:

all'epoca (beh, 4 anni fa) me la cavavo bene, l'assembly del mips mi ha fruttato il mio unico 30 fino ad ora :)