# abs (x) "zu fuß" realisieren



## Anja. (20. Nov 2010)

Abend!
Man soll die funktion abs(x), also den batrag von x zu fuss so gut wie neu erfinden. 
dabei darf man keine If/Else und Schleifen verwenden. Es dürfen lediglich nur die logischen und arithmetischen Operationen verwendet werden. Also: !, ~, &, ^, |, + , << , >> , >>> .
Das heisst man darf logik anwenden und rumShiften.das ganze soll iwie halbwegs nach java code aussehen. 

Meine unglaublich "kreativen" Überlegungen:

Was ist zu tun? 
Als beispiel. Zwei beliebeige zahlen, zur veranschaulichung eine negativ, eine positiv:
1110
0110
. 
von diesen soll nun der betrag ermittelt werden. 
die positive zahl hat positiv zu bleiben, die nagative hat positiv zu werden.
d.h. man suche eine funktion,( dargestellt nur mit log.op. und rumshiften), die eine mit 0 als hochwärtigstes bit anfangende Zahl nicht verändert, und eine mit 1 als hochwärtigstes bit anfangende zahl invertiert und eine 1 draufaddiert. 
es geht um ints, also 32 bit darstellung, hier als bsp nur 4 bit-
negative zahlen liegen als komplemente vor, mit ner 1 ganz links, 
positive mit ner 0 ganz links.

aus der 1110 ist also eine 0010 zu machen,  (0001+0001)
aus der 0110 ist eine 0110 beizubehlaten. 
Wat nun? eine funktion, zwei zahlen. eine zahl ändert sich, eine nicht.
es wird wohl etwas mit dem vorzeichenbit zu tun haben.
hier nun meine crazy idea:

das vorzeichenbit kann man ja leicht extrahieren. 31 mal nach rechts schiften und tada, da haben wirs. 
nennen wird das X
unsere zahl, von der wir nicht wissen ob sie negativ oder positiv ist, nennen wir N
ist das vorzeichen bit 0, also die zahl positiv, so können wir diese 0 beliebig oft draufaddieren, das neutrale additionselement tut dem nix.
ist es jedoch 1, so verändert es die zahl. grob schonmal was wir wollten. positive zahl bleibt, negative ändert sich. desweiteren wirds um diese addition gehen, also die positive zahl wird nicht mehr erwähnt.
desweiteren nehmen wir uns das ganz rechte bit der neg.zahl. bei 1110 ist es die 0.
das extrahieren wir mit & 0001 . also wird s zu 0000. hier wird X draufaddiert. also 1. 
0001 kommt raus. somit habe ich das rechte bit ivertiert... weiter shifte ich meine 0001 Makse um 1 nach linbks.. << ... also 0010.. und wende nun das an: n& 0010 wird zu 0010, hier eine um 1 nach links geshiftete 1 draufaddieren, kommt 0100... die zweite von links 1 muss nun ersetzt werden durch die 0. grob gesagt, was ich machen will, alle bits einzeln zu invertieren mithilfe von +1 immer weiter nachlinks geshiftet... ja, genau, alle 32 bit einzeln invertieren und dann iwie zusammensetzen zu der gesamten invertierten zahl. und dann nur noch wieder ein X also ne 1 draufaddieren und TADA! hab ich den betrag meiner zahl... und die positive hat sich nicht geändert, da füer die  X=0 war und die sich eben nicht dadurch ändert.... joa, das ganze nur noch vernünftig ausgeschrieben.. und.. ehm.. iwie formalisiert... würde ziemlich viel quark glaub ich ergeben, aber in meinem kopf funktionerts.


Liebe Leute, heft mir doch bitte  aus meinem Wahnsinn... 
das da oben dürfte ja krertiv aber bestimmt false sein, oder ? 
popotritt in die richtige richtung wäre sehr willkommen... danke im vorraus.... puh...


----------



## XHelp (20. Nov 2010)

Um ehrlich zu sein konnte ich deinem Ansatz nicht so ganz folgen...
Du braucht für die Lösung ein paar Überlegungen:
1. Eine Zahl, bei welcher alle Bits 0 sind, ist 0
2. Eine Zahl, bei welcher alle Bits 1 sind, ist -1
3. XOR Operator:

```
11100110
XOR 00000000
=   11100110
d.h. die Zahl bleibt unverändert.

    11100110
XOR 11111111
=   00011001
d.h. es wird ein Komplement gebildet
```

Zu der Vorgehensweise:

```
x
```
 ist unsere Zahl, von der wir den Betrag berechnen müssen.
Wie du schon richtig bemerkt hast, kommst du an das Vorzeichen, wenn du die Zahl inkl. Vorzeichen 31 mal nach rechts shiftest. Nennen wir die Zahl mal
	
	
	
	





```
v
```
 für Vorzeichen. Es kann entweder 0 (positiv) oder 1 (negativ) sein.
Dieses 
	
	
	
	





```
v
```
 können wir jetzt von 
	
	
	
	





```
x
```
 abziehen. Wenn 
	
	
	
	





```
x
```
 negativ ist, dann wird -1 gerechnet, wenn positiv, dann bleibt es wie gehabt.
Nun müssen wir das Komplement bilden, aber nur dann, wenn die Zahl negativ ist. Da kommt die 3. Überlegung ins Spiel. Wir müssen also entweder mit 0 (bei positiven Zahlen) oder -1 (bei negativen) XORer. Unschwer erkennbar brauchen wir die Zahl 
	
	
	
	





```
0-v
```
Also sieht das ganze ungefähr so aus:

```
public int abs(int x) {
  int v = x>>>31;
  x=x-v;
  return x^(0-v);
}
```


----------



## Anja. (20. Nov 2010)

Vielen Dank immerhin für den versuch meine quarkideen zu verstehen... 
Deine Idee ist klar, 
leider ist kein "-" zeichen erlaubt in der aufgabe erlaubt
ich hatte ebenfalls eine lösund mit *, doch ist auch das nicht erlaubt.. überlege jetzt die idee beizubehalten und - zu umegehn...
EDIT:
so kann man doch statt 0-v auch das 2-komplemet davon bilden.d.h. man invertiert alles un addiert 1 dazu... wo 0001 war... wird 1110.. +1 ist 1111 also das war wir wollten.. wo 0000 war, wird 1111, .. +1 wird zu 0000, da die 1 im überlauf..




zudem.. vestehe ich nicht ganz warum beim Xor mit 11111111 bei dir steht "es wird ein komplement gebildet", wenn doch nur invertiert wird... oder ist damit das einer komplement gemeint ?


----------



## Landei (20. Nov 2010)

Blödsinnnige Aufgabe.


```
private static int abs(int v) {
        int mask = v >> 32 + 0xFFFFFFFF;
        return (v + mask) ^ mask;
    }
```

Siehe Bit Twiddling Hacks


----------

