7
\$\begingroup\$

This is a homework assignment problem and I tried to solve this all last night but I am still a newbie in Assembly language.

Dont give me the full solution, just give me a hint.

Design an ARM Assembly Language program that will examine a 32-bit value stored in R1 and count the number of contiguous sequences of 1s. For example, the value: 01110001000111101100011100011111 contains six sequences of 1s.

Write the final value in register, R2.

Now, the algorithm I think is to read each character one by one, and increase i by 1 everytime it faces 2 continuous 1s. But how to do it in Assembly Language?

\$\endgroup\$
  • 2
    \$\begingroup\$ Your last paragraph seems a little off the mark to me. But I'm not sure just how much of a hint you want, so I'll just say this: The important thing to look for is when two adjacent bits are different, not the same. Think about what would happen if you took a copy of the data in R1, shifted it by one bit and XORed it with the original value. \$\endgroup\$ – Dave Tweed Sep 2 '12 at 1:21
  • 1
    \$\begingroup\$ In your ISA there should be definitely a instruction to bit rotate through carry. First you clear the carry flag. And then you could simply rotate it left/right and inspect the value of carry flag. Then that carry value will input to your state machine. Code a simple state machine for that. \$\endgroup\$ – Standard Sandun Sep 2 '12 at 1:23
  • \$\begingroup\$ And remember that a register contains 0 and 1 bits, not the characters 0 and 1. You should be looking at the bit-wise operators, including the shift instructions. \$\endgroup\$ – Joe Hass Sep 2 '12 at 1:24
  • 2
    \$\begingroup\$ If you are new to asm but not to let's say C: write C code that solves the problem, then (hand-) translate that to asm step by step. \$\endgroup\$ – Wouter van Ooijen Sep 2 '12 at 7:23
  • 3
    \$\begingroup\$ @WoutervanOoijen I've even found a program that does this C->asm translation automatically... \$\endgroup\$ – markrages Sep 2 '12 at 22:44
10
\$\begingroup\$

Write a loop to shift the word left or right (doesn't matter) until the word is all zeros. The carry flag gives you the value of the next bit.

If carry is 1 and the previous carry was zero you're starting a new sequence of 1s. Then set a previous-was-a-first-one flag. (I assume that by contiguous you mean at least 2.)

If carry is 1 and previous-was-a-first-one is set you have a contiguous series, and increment your counter. Clear the previous-was-a-first-one flag.

If carry is 0 then clear the previous-was-a-first-one.

edit
Apparently "contiguous" doesn't require more than 1 bit, and then it's even simpler:

Set `previous' to `0`.
Shift left until word is all zeros.
If `carry` = `1` and `previous` = `0` increment counter.
Set `previous` to `carry`.
\$\endgroup\$
  • 1
    \$\begingroup\$ Why would you presume "at least 2" when the example he gave included a sequence of just one 1? \$\endgroup\$ – Dave Tweed Sep 2 '12 at 16:17
  • 4
    \$\begingroup\$ @Dave - There's an isolated '1' in the example, but he doesn't say if he counts that as a contiguous sequence. Now English is not even my second language, but my third, so bear with me, but IMO "contiguous" surmises at least two in succession. \$\endgroup\$ – stevenvh Sep 2 '12 at 16:22
  • 3
    \$\begingroup\$ @Dave - Contiguous: 1."touching along the side or boundary; in contact" 2. "physically adjacent; neighbouring" 3. "preceding or following in time" \$\endgroup\$ – stevenvh Sep 2 '12 at 16:24
  • 1
    \$\begingroup\$ yes, he did -- he said that the example included six strings, so obviously he's counting the isolated '1' \$\endgroup\$ – Dave Tweed Sep 2 '12 at 16:46
  • 1
    \$\begingroup\$ @Dave - Indeed he did. "Contiguous" seems to be a highly stretchable concept :-). Updated my answer. Thanks for the feedback. \$\endgroup\$ – stevenvh Sep 2 '12 at 16:52
1
\$\begingroup\$

Here's a solution that iterates over the number of strings, rather than the number of bits in the word. Since I'm not really familiar with ARM assembly language, I'll give it in C. Since it only uses bitwise operators, it'll translate pretty much directly into assembly code.

int nstrings (unsigned long int x)
{
   int result = 0;

   /* convert x into a word that has a '1' for every transition from
    * 0 to 1 or 1 to 0 in the original word.
    */
   x ^= (x << 1);

   /* every pair of ones in the new word represents a string of ones in
    * the original word. Remove them two at a time and keep count.
    */
   while (x) {
     /* remove the lowest set bit from x; this represents the start of a
      * string of ones.
      */
     x &= ~(x & -x);
     ++result;

     /* remove the next set bit from x; this represents the end of that
      * string of ones.
      */
     x &= ~(x & -x);
   }
   return result;
}
\$\endgroup\$
1
\$\begingroup\$

Just suggestion as asked. You need to shift throught each bits, this can be done by shifting the number to the right. Before shifting, check the value of the rightmost bit, this can be achieved by the operation AND with the costant 1. Use some temp to store the last value checked, to increment a counter on the "rising edge" ie when the previous value change from 0 to 1, in pseudo code

SET T1=0
SET CNT=0
WHILE INPUT != 0 DO
    IF INPUT AND 1 != 0 AND T1 == 0 INC CNT
    T1 =  INPUT AND 1
    RIGHT SHIFT INPUT
END WHILE
\$\endgroup\$
0
\$\begingroup\$
  1. A given register X will have the result. Init it with zero.
  2. Take the original value to be processed and store it in two registers, say A and B.
  3. Rotate A to the right one bit, do a XOR of A with B, put the result in A.
  4. Apply a 1h mask to A, putting the result in B.
  5. Sum B to X.
  6. Shift A one bit to the right and, if not zero, loop to step 4
  7. Divide X by 2 (shift it right one bit)

This works because the result of the XOR in step 3 will have a pair of 1's at each point in which there was a transition. So if you then count how many 1's you have, and divide it by 2, you'll have how many transitions there were. Which gives you the number of blocks of consecutive values.

Now, if X results in 0 you either have all 1's or all 0's. So you could start by checking if the original value is 0 and returning imediately with zero in such case, without even runing the steps above. If it is not, and X is 0, you return 1. If not, you divide it by 2 again (since the number of blocks with 1 has to be half the number of distinct blocks, of course).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.