8 Replies - 4424 Views - Last Post: 10 October 2009 - 08:07 PM

#1 ADHDassassin  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 15-September 09

MIPS programming help

Posted 25 September 2009 - 04:52 PM

I have some homework using MIPS that states this:

Initialize one register to a bit value that represents a positive 32-bit integer from keyboard input. Now the program determines how many 1 bits are in the pattern. So the bit pattern: 0000 0000 1001 1000 1110 1010 0101 0011 (i.e. 0x98EA53 in hexadecimal or 10021459 in decimal format) has 12 bits for 1 and 20 bits for 0.

FIRST of all I am not asking for someone to do this for me, but I don't know how to approach this problem. I have been racking my brain for what kinds of bitwise operators I could use in loops and I'm just not getting it?

What kind of operator could be used to determine the number of of 1 bits?

I was thinking of some kind of combination of shift and AND but I'm not sure how it could work

Is This A Good Question/Topic? 0
  • +

Replies To: MIPS programming help

#2 wildgoose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 67
  • View blog
  • Posts: 468
  • Joined: 29-June 09

Re: MIPS programming help

Posted 25 September 2009 - 07:32 PM

Slow method....
 unsigned int dw;

  cnt = 0
  while (dw)
  {
	  cnt += (dw & 1)
	  dw >>= 1
   }




Fast Method (Untested, just did it in the editor. probably needs reworkingn!

  ;ebx=data

	mov al,0
	clc
$L1:
   adc al,0		 ; al = al + 0 + carry
	mov ecx,0
	bsf ecx,ebx	 ; ecx=bit position
	shr ebx,cl	   ; Shift bit out into carry
	jc $L1

	;al = count


Was This Post Helpful? 0
  • +
  • -

#3 ADHDassassin  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 15-September 09

Re: MIPS programming help

Posted 27 September 2009 - 04:23 PM

what assembly language are you using?
because I don't quite understand what is going on in these snippets
Was This Post Helpful? 0
  • +
  • -

#4 wildgoose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 67
  • View blog
  • Posts: 468
  • Joined: 29-June 09

Re: MIPS programming help

Posted 27 September 2009 - 09:10 PM

Sorry, I must have been really really tired.
You need MIPS and I put 80x86.

That 1st snippet is C.
It essentially loops while the value is a non-zero value. You don't care about which bits are set, only the number of bits set. So if non-zero, tests the LSB (Least Significant Bit) for non-zero and if set then adds one.

But I cheated. Technically the conditional check of (dw & 1) leaves a value of 1 or 0 and I merely summed that onto the tally. Didn't need a branch. I shift the LSB out, then I loop back up and test to see if any bits remained by the whole value not being zero. It is important to make sure you use a Logical Shift Right and not an Arithmetic Shift Right.

A Logical shift Right stuffs 0 into the MSB and shifts the LSB into the carry.
An Arithmetic Shift Right uses what I call a sticky bit. The MSB is shifted right but also stays in the MSB. If a number is negative a 1 is in the MSB, and if positive or zero, a 0 is in the MSB. In this codes case, if you are using an Arithmetic Shift then the code will never end as it will continuously be shifting 1's forever!


The 80x86 assembly took advantage of an instruction that returned the bit # of the first bit set! But ignore that since I don't remember there being an equivalent instruction on the MIPS.

This post has been edited by wildgoose: 27 September 2009 - 09:14 PM

Was This Post Helpful? 0
  • +
  • -

#5 dunn0277  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 08-October 09

Re: MIPS programming help

Posted 10 October 2009 - 08:10 AM

Alright its been about a year since i programmed in MIPS, and also my first post on dreamincode, but this is my logic behind it.

Given value, 0000 0000 1001 1000 1110 1010 0101 0011 = val.


main:

#Load the value into a register
lw $s0, val
#counter to check for end of val
li $s2, 1

#Branch to check next value
checkNext:

#branch if counter is equal to 32
beq $s2, 32, end

#Load the bit in the zero postion and store into $t0
lbu $t0, $s0($zero)



srl = Shift right logical, i have found this very useful, the way it works is you take the value stored in $s0 and rotate the first bit all the way to the end of the value for example if we had the value 1011 stored into $s1 and we did the line of code srl $s1, $s1, 1.. $s1 would be now be 0111
*Note* you can rotate as many bits as you would like srl $s1, $s1, <this is the number of bits being rotated>

#shift first bit all the way to the end of the 32 bit value
srl $s0, $s0, 1

#increase counter $s2 by 1,  branch if value in $t0 != 1
addiu $s2, $s2, 1
bne $t0, 1, checkNext

#Else addiu (add immediate unsigned) when $t0 =1
addiu $s1, $s1, 1

#jump to check next bit
j checkNext

#continue to print
end:
# this portion is were you can print out the val which is now back to its #original value because of the number of bit we rotated int he program.
#while $s1 now contains the number of ones in the Value.

# infinite loop
exit:
j exit




This is a most of the solution to your problem, not that the following code doesn't contain the .data section and .text section at the top, so that must be added..... i hope this helped clear up some of your problems.
Was This Post Helpful? 0
  • +
  • -

#6 wildgoose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 67
  • View blog
  • Posts: 468
  • Joined: 29-June 09

Re: MIPS programming help

Posted 10 October 2009 - 09:35 AM

I'm not the welcoming commitee, but welcome aboard Dunn0277!

It's been 3 months since the original post so definitely outside the homework due window,

BUT, you need to be careful in your posts! A LOT of people post here looking for people to do their homework for them. They act coy, blame their professors and what not, act unclear like they don't understand the response, etc. so to get us to do their homework solution for them. There was a reason I gave this poster a pseudo solution in another assembly language. If they had actually posted code, it would have been debugged to some degree dependent upon how manageable, clean, and organized it was.

As you read posts you'll see responses from many readers about following the rules, and post their code first, etc.!

But then again this is three months later, too late to help the original poster with their homework!

As to your code snippet, you're double branching 32 times. You should not spend time testing for 32, test to see if the value of the remaining bits is zero. If so, then you're done! By using the logical shift right instead of an arithmetic shift right you are clearing the bits so when you find the last bit, you're done! Also, you're double branching. You jump up then test! Try jumping over the code to the bottom of the loop and do your test there! Then you branch up, or fall out of the loop. One jump instead of two, thus faster code!

I too used to program in MIPS all the time, now its only occasionally writing SIMD code for the PSP, and some code snippets on these learning websites.
;lbu $t0, $s0($zero)
lbu $t0, 0,($s0)


You were close. Not the zero register, an offset value of 0. And the register goes inside the parenthesis to indicate load an unsigned 8-bit value in memory addressed by $s0 + 0 offset.


Have a good weekend!

This post has been edited by wildgoose: 10 October 2009 - 09:46 AM

Was This Post Helpful? 0
  • +
  • -

#7 dunn0277  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 08-October 09

Re: MIPS programming help

Posted 10 October 2009 - 01:47 PM

Ah.... i didn't mean to use srl, I meant to sure the ror (Rotate Right), instead of srl. to keep the original binary value in memory in order to print out the correct value of the input along with the number of ones.

Thanks for catching my mistake though.
Was This Post Helpful? 0
  • +
  • -

#8 wildgoose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 67
  • View blog
  • Posts: 468
  • Joined: 29-June 09

Re: MIPS programming help

Posted 10 October 2009 - 02:08 PM

But with 32 registers, go ahead and waste the register!
I'm only saying, the reason you write code in assembly is to make code go FAST! Not just write regular program code. 20 years ago, assembly was the best option. Now days, some high level language like C or C++. Leave the self contained libraries and speed bottle necks for the assembly code after other avenues of optimization have been exhausted!

ror is a powerful instruction on many processors, but in this particular programming problem, you chose the right logical shift correctly! Only you needed to test for non-zero for the loop. If the value was a 1. Your code takes 64 jumps! Using the method I indicated, it would have taken 1. The initial jump to bottom of loop, then only one per loop after the LSB is latched out. If the MSB is set, then 1+32 jumps intead of 64.

This post has been edited by wildgoose: 10 October 2009 - 02:12 PM

Was This Post Helpful? 0
  • +
  • -

#9 dunn0277  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 08-October 09

Re: MIPS programming help

Posted 10 October 2009 - 08:07 PM

Good point, thanks for the correction its been awhile since i thought in assembly. I have to get my mind back up to speed
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1