3
$\begingroup$

Little time ago I started to playing with binary numbers and just have a little fun . I found some pretty interesting things. I want to ask if my own findings have some official names or no .Also I would like to get help with finding proofs. All of my finding are related to numbers with fixed maximum value, just like in the computer.

So the first interesting thing I found is 'bitwise negation' operation for non binary numbers.

we already know definition of bitwise negation operator for binary numbers, every 1 became 0 and every 0 became 1 .

It is also can be written by this form : $x' = 2^r -1 -x $

$ r=\text{number of bites} $

$ x=\text{variable}$

$ x'=\text{bitwise negated value of variable in binary form}$

This is true , because the sum of the number and it's negative is always equal to $2^r-1$ .

I trought ,we could make this operations happen in another number systems simply by replacing base .

So the following equation would work :

$x' = b^r-1 -x$

where

$b=\text{ base}$

So for example , the 'bitwise negation' of decimal number 1250 with 4 digits would be

9999-1250 = 8749


I also 'invented' my own addition pattern, which I will be explaining right now.

The new addition system Im calling 'reflow' instread of overflow, because every bit which is overflowing , will be moved to the right side.

Imagine having two numbers with 4 bits each . Both of them have value of 1000 When you add then in normal addition, it will overflow , and the result will be 0000

  1000
 +1000
1|0000    | this sign means, it is overflowed

but in my operation it would reflow, which means following.

  1000
 +1000 
1|0000 = 0001
└────╝

I also writed it in form of equation :

$a➕c = a+c- \lfloor \frac{a+c}{b^r}\rfloor(b^r-1)$

a,c = variables

b = base (decimal = 10 , binary =2 etc)

r = number of digits, bits


I was studying this a little bit and I surprisingly found, that in every case , in interval $[0,b^r-2]$ there is true that :

$n➕m= (n'➕m')'$

we suppose that :

$G=b^r$

$g=b^r-1$

So expanded it is:

$n+m-g\lfloor\frac{n+m}{G}\rfloor = g-(g-n+g-m-g\lfloor\frac{g-n+g-m}{G}\rfloor)$

$n+m-g\lfloor\frac{n+m}{G}\rfloor=g-(2g-n-m-g\lfloor\frac{2g-n-m}{G}\rfloor)$

$n+m-g\lfloor\frac{n+m}{G}\rfloor=-g+n+m+g\lfloor\frac{2g-n-m}{G}\rfloor $

$-g\lfloor\frac{n+m}{G}\rfloor=g(\lfloor\frac{2g-n-m}{G}\rfloor-1)$

$-\lfloor\frac{n+m}{G}\rfloor = \lfloor\frac{2g-n-m}{G}\rfloor-1$

$\lfloor\frac{2g-n-m}{G}\rfloor+\lfloor\frac{n+m}{G}\rfloor=1$

What next guys? I already tried to ask here to solve just this equation, this is the response LINK but the result is completely oposite to what i was looking for. The result is exactly when it shouldnt be true.. Did I made some problem while solving it?

Here is also link to Desmos graphing tool with some of the formulas LINK

 Thank you for your responses
     Patrik Bašo
$\endgroup$
  • 1
    $\begingroup$ Your "bitwise negation" of a decimal number is called its nines' complement. $\endgroup$ – FredH Mar 31 at 20:24
1
$\begingroup$

You've done pretty well in your proof, which requires just one extra step.

If $\ m+n \le g-1\ $, then $$\ 2G>2g\ge 2g-n-m \ge g+1= G .$$ Thus, since $\ 2G>2g-n-m\ge G\ $ in this case, you have $\ \lfloor\frac{2g-n-m}{G}\rfloor=1\ $, $\ \lfloor\frac{n+m}{G}\rfloor=0\ $, and $\lfloor\frac{2g-n-m}{G}\rfloor+\lfloor\frac{n+m}{G}\rfloor=1\ .$

On the other hand, if $\ m+n>g-1\ $, then (because $\ m,n < g\ $): $$0<2g-n-m<g+1=G\ ,$$ and so $\ \lfloor\frac{2g-n-m}{G}\rfloor=0\ $, $\ \lfloor\frac{n+m}{G}\rfloor=1\ $, and $\lfloor\frac{2g-n-m}{G}\rfloor+\lfloor\frac{n+m}{G}\rfloor=1\ .$

One thing you should be made aware of, however, is that when writing out proofs, you should avoid just writing down the equation you're trying to prove and manipulating it into something which is purportedly equivalent. The main reason why this is inadvisable is the that the flow of logic is wrong: $$\ \left[\matrix{\mbox{Proposition}\\ \mbox{to be proved}}\right]\implies P_2\implies P_3\implies \dots \implies\left[\matrix{\mbox{True}\\ \mbox{Proposition}}\right]\ ,$$ and the final proposition will be equivalent to the original only if every step in your manipulation is reversible. If that does happen to be true, then you will be able to reverse the implications in the above chain of propositions to obtain a valid proof: $$\ \left[\matrix{\mbox{True}\\ \mbox{propostion}}\right]\implies \dots \implies P_3\implies P_2 \implies\left[\matrix{\mbox{Proposition}\\ \mbox{to be proved}}\right]\ ,$$ and this is the form which any proof you give should take.

As it turns out, your addition, $\ "➕"\ $, is essentially the same thing as addition modulo $\ b^r-1\ $: $$ a➕c \equiv a+c \pmod{b^r-1}\ .$$ Your negation is also the same as negation modulo $\ b^r-1\ $: $$ m'\equiv -m \pmod{b^r-1}\ .$$ So your observation that $\ n➕m= (n'➕m')'\ $ is equivalent to the equation: $$ m+n\equiv -\left(\left(-m\right)+\left(-n\right)\right) \pmod{b^r-1}\ ,$$ which is not difficult to prove using modular arithmetic.

$\endgroup$
  • $\begingroup$ Thank you man, I already solved it too , Then I will add my conclusion which is a little more easier I think, So would you look at it then? $\endgroup$ – Patrik Bašo Apr 1 at 10:29
  • $\begingroup$ Thank you for your answer,it really helped me , $\endgroup$ – Patrik Bašo Apr 1 at 10:34

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.