Re: Reducing binary representation
- To: mathgroup at smc.vnet.net
- Subject: [mg57175] Re: Reducing binary representation
- From: dh <dh at metrohm.ch>
- Date: Fri, 20 May 2005 04:43:08 -0400 (EDT)
- References: <d6heg9$d24$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Hi Torsten,
We start with an arbitrary integer and get its binary digits.
"Split" gives us lists of repeated digits.
We replace runs of 1's by lists of equal length with a marker 2/3 at the
high/low order bit. Finally we "Flatten" to get a single list t1.
Bits with marker 2 must be multiplied by 2 and bits with marker 3 mark
negative nummbers.
n = 1324;
t1 = Split[
IntegerDigits[n, 2] ] /. x : {1, (1) ..} :> ({2, Table[0, {Length[x] -
2}], 3}) // Flatten;
From List t1 we get a list t2 with only the not-marked bits. And a
third list t3 with the bits we must multiply by 2.
To have space for the multiplication by 2, we expand both lists by an
additional high order digit of 0.
Finally we multiply list t3 by bit-shift and add both lists. This gives
the non negative numbers.
t2 = Prepend[t1 /. {2 -> 0, 3 -> 0}, 0];
t3 = Prepend[t1 /. {3 -> 0, 1 -> 0}, 0];
t3 = RotateLeft[t3] /. {2 -> 1};
t2 = t2 + t3;
From t1 we obtain the list with only the negative numbers and pad
again with a zero.
t3 = Prepend[t1 /. {2 -> 0, 1 -> 0, 3 -> 1},0];
Now we have the exponents of the pos.and neg. numbers and create the output
i = 0; t2 = (HoldForm[2^#] &)[i++ ]# & /@ Reverse[t2]
i = 0; t3 = (HoldForm[2^#] &)[i++ ]# & /@ Reverse[t3]
Plus @@ (t2 - t3)
Sincerely, Daniel
Torsten Coym wrote:
> Hi MathGroup,
>
> I want to reduce the number of coefficients in the binary representation
> of arbitrary integer numbers. I managed to convert an integer number
> into a sum of powers of two in the following way:
>
> In[7]:=
> ToBinary[x_, n_] := Plus @@
> Sequence[MapThread[Times,
> {Table[(HoldForm[2^#1] & )[i], {i, n - 1, 0, -1}],
> IntegerDigits[x, 2, n]}]]
>
> In[8]:=
> ToBinary[121, 10]
>
> Out[8]=
> HoldForm[2^0] + HoldForm[2^3] + HoldForm[2^4] +
> HoldForm[2^5] + HoldForm[2^6]
>
> The sum of adjacent powers of two can be reduced as follows:
>
> In[9]:=
> Sum[2^i, {i, k, j}]
>
> Out[9]=
> 2^(1 + j) - 2^k
>
> I now want to apply that to the binary number representation, so that
> 121 will become
>
> 2^7-2^3+2^0
>
> but I cannont figure out how to do this. If I release the Hold[]
> Mathematica just evaluates all the terms containing "2" to get "121",
> which is not what I want ;)
>
> Unfortunately I have no idea how to tackle this kind of problem. Any
> suggestion would be appreciated.
> Thank you.
>
> Torsten
>