• C

adding bytes

I have an array in the form of char array[200].  Is there a way that i can add up the parts of the array in binary form to get on big long binary number and then divide it by another binary number?  I think you have to use bitwise functions, but i am not sure.

Darts
dartslcaAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

nils pipenbrinckCommented:
that's really easy to do:

at first you should write yourself a couple of routines to do add, subtract, binary shift and so on for your array numbers..

here is a couple of them:

void add (unsigned char * sum, unsigned char *a, unsigned char *b)
{
  // add two values
  int carry = 0;
  for ( int i=200; i; i--)
  {
    int c = (int)a[i-1] + (int)b[-1] + carry;
    carry=0;
    if ( c>256 ) carry = 1;
    sum[i-1] = c&255;
  }
}

void sub (unsigned char * sum, unsigned char *a, unsigned char *b)
{
  // subtract two values
  int carry = 0;
  for ( int i=200; i; i--)
  {
    int c = (int)a[i-1] - (int)b[-1] - carry;
    carry=0;
    if ( c<0 ) carry = 1;
    sum[i-1] = c&255;
  }
}

void shift (unsigned char * val)
{
  // shift by one to the right.
  int carry = 0;
  for ( int i=0; i<200; i++)
  {
    int oldcarry = carry;
    if ( val[i]&1 ) carry = 1;
    val[i]>>=1;
    if ( oldcarry ) val[i]|=128;
  }
}


the trick is, that you do it like you would calculate an addition on paper (you learned that in school I think).

you need a variable to hold the carry value since c doesn't have something like that.

when you want to do division follow the steps on this webpage:

http://hsc.csu.edu.au/compstud/courses/23unit/comptech/97/division.htm

they explain how to do division by using more simple arithmetic (say shifts and subracts).. the web page is really cool..


I hope this helps.. if not let me know..

(btw. i haven't checked the code I wrote, but I'm pretty sure it works.. don't flame me if I made a typo)

  Nils
0
nils pipenbrinckCommented:
0
aperdonCommented:
Division can be done with substracting. The number of times substraction did not result in less than zero, is the answer to the division.
0
Determine the Perfect Price for Your IT Services

Do you wonder if your IT business is truly profitable or if you should raise your prices? Learn how to calculate your overhead burden with our free interactive tool and use it to determine the right price for your IT services. Download your free eBook now!

dartslcaAuthor Commented:
I can't understand what you are trying to do?  Whats the carryold and carry value do, where does it affect anything?  Can you help me understand what you wrote?  I only have one array of chars of max length 200, but the array isn't always 200.  I need to add up the binary values of all the bytes in the array and then divide that number by a constant 16-bit binary number and append the remainder of that division to the end of the array somehow.
0
nils pipenbrinckCommented:
ok. the carry thing is used as a reminder of a overflow of two additions.

if you add two bytes your result may not fit into a byte anymore. In this case you can use a carry to remind that the last addition was overflowed and add the carry to the next addition.

one example in decimal:

    24
   +38
   ----


first you add the least significant numbers (4 and 8). the result is 12. since 12 is more than 9 (the most significant number in decimal) you set the least significant number of the sum to 2 and set your carry to one. (the carry is just used to signal, that the _last_ addition overflowed).

now you add the next significant numbers (2 and 3) and also add the carry to it (1 in this case since the last addition overflowed. otherwise it should be zero). the result is 6 and fits into a decimal number.

thus the addition of the two values gives you a result of 62. (surprise!)



when you work with large binary numbers you do it almost identical as in the example above.. instead of "decimal numbers" you work with bytes... and the addition of two bytes overflows when the value exceeds 255. I guess that's enough to understand how addition of binary numbers works. (you can also do it bit by bit or dword by dword. the way to code it is all the same).

writing a addition algorithm for large binary numbers shouldn't be no problem anymore.


now to subtraction.. it's just like addition, but instead of setting your carry to one when the result is greater than 255 you set it to 1 when your result drops below zero. the carry is then subtracted from the next significant subtraction..

everything is identical to the way kids lern arithmetics in school.. the only difference is, that kids do it in decimal, and we work with bytes.


now you have to tackle the division.. there's one very important special case in division of binary numbers.. it's the case when you divide your number by two.. in this case you can simply shift all bits to the right by one bit position..

in binary the number 193 is:
 

   11000001

 shift it to the right by one gives you:

    1100000

 (the least significant bits just goes into nirvana..)

 the result of this value is (surprise!): 96

writing a shift by right for binary numbers shouldn't be a problem. you only have to make sure, that only the last bits goes into nirvana. the other bits move into the highest bit position of their less significant byte..

(take a look at my code.. it should make it clear how it works).


if you have these simple arithmetics you can build multiplication and division by any size numbers... I'll give you a pseudo-code how to do this in a couple of minutes.. ( I just have to call someone..)

back in a minute,
  Nils







0
aperdonCommented:
So the array contains all 0's and 1's?

In this case do:

unsigned short sum = 0;

for (i = 0; i < 200; i++)
{
   sum <<= 1;
   sum += bit[i];
}

where bit[199] is msb and bit[0]=lsb

then div = sum / constant;

after this you must convert the 10-based number to binary.

pos = 1;
for (i = 0; i >= 0; i--)
{
   bit[i] = div & pos;
   pos *= 2;
}

0
nils pipenbrinckCommented:
aperdon: he's doing arithmetic on values way beyond 32 bits (640 bits in his example)..


to the division.. I just once again took a look at the web-site I already gave you... I can't explain any better how to do it...

once again the url.. please take a look at it... they have an example in decimal (to understand how it works) and a binary example (which can directly converted into an algorithm)..


all it does is addition, subtraction, shift and compare operations (and all the time they use a carry to "remember" the "overflow" from the last operation.

nils



http://hsc.csu.edu.au/compstud/courses/23unit/comptech/97/division.htm
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
aperdonCommented:
ok, i forgot.

but he is doing 200bytes.
just split it into 8 longs of 32-bit

this means after every 32 bits start a new long

unsigned long sum[8];
int l = 0;
for (i = 0; i < 8; i++) sum[i] = 0;
for (i = 0; i < 200; i++)
{
   sum[l] <<= 1;
   sum[l] += bit[i];
   if (i & 31) l++;
}

0
dartslcaAuthor Commented:
Thanks Nils,

I understand it better now.  I think I almost have it done it code, just having a little trouble with the variable overflow, do you know of a bigger value i can use besides unsigned char that would work?  But i think i am just about done.  Thanks again.

Darts
0
nils pipenbrinckCommented:
jep..
unsigned long will also work..
and the bigest value you can express using unsigned long is 0xffffffff.

the problem is, that the addition generated by your c-compiler itself will overflow.

expressing bit numbers as bytes is no problem. you could gain some percent of performance with larger elements, but it's not worth the work.

nils


0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.