/prog/ - Bitwise operation

Name: Anonymous 2010-06-09 5:28

How are simple operations like adding and subtraction represented using only bitwise operators such as &, |, ^, >>, ~, and <<?

Also, do each of the bitwise operators perform at the same rate, or are some faster than others?

Name: Anonymous 2010-06-09 5:31

http://en.wikipedia.org/wiki/Arithmetic_logic_unit#Complex_operations

Name: Anonymous 2010-06-09 5:50

Read SICP

Name: Anonymous 2010-06-09 5:59

>>3
http://www.google.com/search?q=site:mitpress.mit.edu/sicp+bitwise

Name: Anonymous 2010-06-09 7:27

>>1
In binary addition, there are 4 combinations that you can make with 0 and 1

1 + 0 = 1 0 + 1 = 1 0 + 0 = 0 1 + 1 = 10

The XOR/^ bitwise operator behaves exactly the same as the addition operator in the first 3 cases

1 XOR 0 = 1 0 XOR 1 = 1 0 XOR 0 = 0 1 XOR 1 = 0

The first 3 cases even work with bigger numbers too (it works because you don't have to carry any 1s)

1000101010 554 + 101000101 325 ============ 1101101111 879 554 + 325 = 879 554 XOR 325 = 879

In our last the case (1 + 1 = 10), how can we use binary operators with 1 and 1 to get 10 and make it work with bigger numbers? I smoked too much weed and cannot post a solution at the time.

Name: Anonymous 2010-06-09 7:28

/me yiffs all over >>3

Name: Anonymous 2010-06-09 8:07

>>4
._.

Name: Anonymous 2010-06-09 8:13

>>1
If only Google had been invented. :(

Name: Anonymous 2010-06-09 8:40

>>8
First you have to invent the Google if you want to make an apple pie from scratch.

Name: Anonymous 2010-06-09 8:45

>>8
I checked google but all it gave me was retarded java shit. Also, see >>4

Name: Anonymous 2010-06-09 10:14

>>10
Consult Google for explanations on how to use Google effectively.
Also, who the fuck cares if you got ``retarded java shit''? Jaev's bitwise operators are exactly the same as C's.

Name: Anonymous 2010-06-09 10:46

>>11
Jaev
;)

Name: Anonymous 2010-06-09 10:58

http://en.wikipedia.org/wiki/Adder_(electronics)

Name: Anonymous 2010-06-09 11:02

>>11
Are there any bitwise operators that don't behave like bitwise operators?

Name: Anonymous 2010-06-09 11:03

>>14
PHP's, probably.
I don't actually know, but it's a safe bet.

Name: Anonymous 2010-06-09 11:07

>>15
$ php -r 'echo 1 ^ 2, "\n";' 3 $ php -r 'echo "1" ^ "2", "\n";' " $ php -r 'echo 1 ^ "2", "\n";' 3 $ php -r 'echo "1" ^ 2, "\n";' 3 $ php -r 'echo "1" ^ "2", "\n";' "

Heh.

Name: Anonymous 2010-06-09 11:50

>>14
Perhaps, Austin Powers: smooth operator.
>>16
It should be printing a ETX char for "1" ^ "2", not sure why you are getting a ". I'm pretty sure it performs the operator the ascii values, i.e.



$ php -r 'echo "yO-ZZV"^"V?_5=y","\n";'

/prog/

Name: Anonymous 2010-06-09 11:52



// here's my crude first attempt.

#include <stdint.h>

#include <stdlib.h>

#include <stdio.h>



typedef uint8_t U;



U plus(U a, U b) {

    U m = 1, am, bm, c=0, s, r=0;

    while(m) {

        am = !!(a & m);

        bm = !!(b & m);

        s = (am ^ bm);

        if(c) {

            if(!s) {

                r |= m;

                c = am & bm;

            }

        } else {

            if(s)

                r |= m;

            c = am & bm;

        }

        printf("m:%16lu am:%lu bm:%lu c:%lu s:%lu r:%lu\n",m,am,bm,c,s,r);

        m <<= 1;

    }

    return r;

}



int main(int argc, char **argv) {

    U a=0,b=0;

    if(argv[1]) {

        a = atoi(argv[1]);

        if(argv[2]) {

            b = atoi(argv[2]);

        }

    }

    printf("%lu + %lu: %lu\n",a,b,plus(a,b));

    return 0;

}

Name: Anonymous 2010-06-09 12:52

>>17
php -r "echo 'ANUS.'^'9/\'=$';"

Name: Anonymous 2010-06-09 14:17

>>18
Did you mean:

      int add(int a, int b){

            if (!a) return b;

            else

                 return add((a & b) << 1, a ^ b);

      }

Name: Anonymous 2010-06-09 14:33

Here's some code I just saw that does a multiplication by 10 using shifts and an addition:

x = (x << 1) + (x << 3)

Or in the original language:

  asl a

  sta $38

  asl a

  asl a

  clc

  adc $38

  sta $38

Name: Anonymous 2010-06-09 14:34

Sorry, last instruction is irrelevant.

Name: Anonymous 2010-06-09 14:43

>>21
You're trying to tell us that 2x + 8x = 10x? I don't believe you.

Name: Anonymous 2010-06-09 14:46

>>23
It's pretty amazing, I ran it over all known natural numbers in GHCi just to make sure.

Name: Anonymous 2010-06-09 14:48

I heard that adding (INT_MAX-1) to a number is like subtracting 1.

Name: Anonymous 2010-06-09 14:50

>>21
Is multiplication operator considered harmful now?

Name: Anonymous 2010-06-09 14:51

>>26
Hi, welcome to a thread on bitwise operations.

Name: Anonymous 2010-06-09 14:54

>>27
Hi, please pay your beet toll.

Name: Anonymous 2010-06-09 15:10

>>28
Poor cover, dude.

Name: Anonymous 2010-06-09 15:13

>>29
Different person.

Name: Anonymous 2010-06-09 15:16

>>30
Then >>28's opinion of >>26 is higher than merited.

Name: Anonymous 2010-06-09 15:17

>>31
I see >>26 as a poor joke that you did not `get', as it were.

Name: Anonymous 2010-06-09 15:19

>>32
I know, hence >>31. Is this discussion so hard for you to follow?

Name: Anonymous 2010-06-09 15:26

>>26
Is multiplication operator considered harmful now?
I think it's slower, it probably works like this:

  sta $4202

  lda #10

  sta $4203

  ; do something else for a while until the multiplication completes

  lda $4216

Name: Anonymous 2010-06-09 15:35

>>33
Please, leave the insults in /b/.

Name: Anonymous 2010-06-09 15:42

>>34
You're going to love finding out about optimizing compilers.

>>35
Fuck your shit.

Name: Anonymous 2010-06-09 16:14

>>36
Back to http://cairnarvon.rotahall.org/, please.

Name: Xarn Fan !AWEsomEEEE 2010-06-09 16:24

>>37
Xarn is /prog/ and /prog/ is Xarn. If you don't like it, back to /pr/, please.

Name: Anonymous 2010-06-09 16:24

>>37
>>36 wasn't a Xarn.

Name: Anonymous 2010-06-09 16:33

BAMPU XARNAE

Name: Anonymous 2010-06-09 16:36

>>40
That's not actually better than the one or two idiots hating on Xarn because they're jealous of the attention he gets (or because they think their imageboard culture can be transplanted onto world4ch).

Name: Anonymous 2010-06-09 16:38

>>41
Are you Xarn? I thought so.

Name: Anonymous 2010-06-09 16:58

>>1
>>,
FUCKINGLY AMAZING

Name: Anonymous 2010-06-09 17:18

>>36
What's a compiler?

Name: Anonymous 2010-06-09 17:22

>>34
what the hell is that?

Name: Anonymous 2010-06-09 17:26

>>20
Did you mean:
[code]int add(int a, int b) {
if (!a) return b;
return add((a & b) << 1, a ^ b);
}

Name: Anonymous 2010-06-09 17:30

So I have found out a few things via googling
assume two unsigned integers a and b:[o]
a + b = ( ( a & b ) << 1 ) + ( a XOR b )[\o]

also

if ( a NAND b ) then ( a + b ) = a XOR b[o]
this is just saying if you don't have to carry while doing binary addition, then a + b is equal to a xor b [o][\o][\o]

So I was thinking about the a + b = a xor b part and realized there must be some way to extrapolate a + b to a sum of terms that where we can then apply the a xor b thing.

Any ideas?

Name: Anonymous 2010-06-09 18:01

assume a and b are the same size and are a list of bits
def a+b:
if size = 1: return (a&b, a^b)
else: return (first(a) + first(b) + first(rest(a)+rest(b)), rest(rest(a)+rest(b)))

Name: Anonymous 2010-06-09 18:49

z = ((x * 0x0101010101010101ULL & 0x8040201008040201ULL) * 

     0x0102040810204081ULL >> 49) & 0x5555 |

    ((y * 0x0101010101010101ULL & 0x8040201008040201ULL) * 

     0x0102040810204081ULL >> 48) & 0xAAAA;

Used this snippet a couple days ago, if you know what it does from just looking at it then you know what you doing.

Name: Anonymous 2010-06-09 19:14

>>49
It uses a bunch of meaningless magic numbers just to interpolate the bits of the result of some transformation of x and y as a short.

Name: Anonymous 2010-06-09 19:20

>>50++

Name: >> !!50++bKT00Wlp00p 2010-06-10 0:58

Name: Anonymous 2010-06-10 4:23

>>50
They aren't meaningless !!

Name: Anonymous 2010-06-10 12:07

>>49,53
Arithmetically interleaving bits!! I don't care!!

Name: Anonymous 2010-06-11 15:17

No need to ask,
He's a smooth operator

Name: Anonymous 2010-06-11 16:40

if (isSmoothOperator()) {

    throw new ParadoxException();

}

Name: Anonymous 2010-06-11 18:27

TOPICS IN ANALYSIS SMOOTH OPERATOR ALGEBRAS AND K-THEORY

Name: Anonymous 2010-06-17 19:44

interesting problem you came across

#include <stdio.h>



int main()

{

    int a,b,q=64;



    for (a=0; a<q; a++) {

        for (b=0; b<q; b++) {

            if ((a + b) == (a ^ b))

                printf("# ");

            else

                printf("  ");

        }

    printf("\n");

    }

    return 0;

}

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

Name: Anonymous 2010-06-17 19:46

#include <stdio.h>



int main()

{

    int a,b,q=64;



    for (a=0; a<q; a++) {

        for (b=0; b<q; b++) {

            if ((a + b) == ((a & b) << 1 ^ (a ^ b)))

                printf("# ");

            else

                printf("  ");

        }

    printf("\n");

    }

    return 0;

}

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

Name: Anonymous 2010-06-17 19:52

>>58 represents the efficiency of the XOR (and OR too) operator as a substitute for the addition operator. It looks like a Sierpinski triangle.

Name: Anonymous 2010-06-17 20:43



uintmax_t plus(uintmax_t a, uintmax_t b)

{ return a && b ? plus(a ^ b, (a & b) << 1) : a | b; }

Name: Anonymous 2010-06-18 0:04

Subtract:



int Sub (int X, int x)

{

    return (((~X & x) << 1) ?

      Sub((~(~X & ~x) & ~(X & x)),((~X & x) << 1)) :

        (~(~X & ~x) & ~(X & x)));

}

Name: Anonymous 2010-06-18 1:13

#include <stdio.h>

int main()
{
    int a,b,q=64;
    float c = 0.0;

    fgetc(stdin);

    for (a=0; a<q; a++) {
      c = a/2;
      while (c > 0) {
      printf(" ");
      c--;
      }
      for (b=0; b<q; b++) {
      if ((a + b) == (a ^ b))
      printf("# ");
      else
      printf(" ");
      }
    printf("\n");
    }
    return 0;
}

Name: Anonymous 2010-12-21 18:58

Name: Anonymous 2011-01-31 20:38

<-- check em dubz

Bitwise operation

1 Name: Anonymous 2010-06-09 5:28

2 Name: Anonymous 2010-06-09 5:31

3 Name: Anonymous 2010-06-09 5:50

4 Name: Anonymous 2010-06-09 5:59

5 Name: Anonymous 2010-06-09 7:27

6 Name: Anonymous 2010-06-09 7:28

7 Name: Anonymous 2010-06-09 8:07

8 Name: Anonymous 2010-06-09 8:13

9 Name: Anonymous 2010-06-09 8:40

10 Name: Anonymous 2010-06-09 8:45

11 Name: Anonymous 2010-06-09 10:14

12 Name: Anonymous 2010-06-09 10:46

13 Name: Anonymous 2010-06-09 10:58

14 Name: Anonymous 2010-06-09 11:02

15 Name: Anonymous 2010-06-09 11:03

16 Name: Anonymous 2010-06-09 11:07

17 Name: Anonymous 2010-06-09 11:50

18 Name: Anonymous 2010-06-09 11:52

19 Name: Anonymous 2010-06-09 12:52

20 Name: Anonymous 2010-06-09 14:17

21 Name: Anonymous 2010-06-09 14:33

22 Name: Anonymous 2010-06-09 14:34

23 Name: Anonymous 2010-06-09 14:43

24 Name: Anonymous 2010-06-09 14:46

25 Name: Anonymous 2010-06-09 14:48

26 Name: Anonymous 2010-06-09 14:50

27 Name: Anonymous 2010-06-09 14:51

28 Name: Anonymous 2010-06-09 14:54

29 Name: Anonymous 2010-06-09 15:10

30 Name: Anonymous 2010-06-09 15:13

31 Name: Anonymous 2010-06-09 15:16

32 Name: Anonymous 2010-06-09 15:17

33 Name: Anonymous 2010-06-09 15:19

34 Name: Anonymous 2010-06-09 15:26

35 Name: Anonymous 2010-06-09 15:35

36 Name: Anonymous 2010-06-09 15:42

37 Name: Anonymous 2010-06-09 16:14

38 Name: Xarn Fan !AWEsomEEEE 2010-06-09 16:24

39 Name: Anonymous 2010-06-09 16:24

40 Name: Anonymous 2010-06-09 16:33

41 Name: Anonymous 2010-06-09 16:36

42 Name: Anonymous 2010-06-09 16:38

43 Name: Anonymous 2010-06-09 16:58

44 Name: Anonymous 2010-06-09 17:18

45 Name: Anonymous 2010-06-09 17:22

46 Name: Anonymous 2010-06-09 17:26

47 Name: Anonymous 2010-06-09 17:30

48 Name: Anonymous 2010-06-09 18:01

49 Name: Anonymous 2010-06-09 18:49

50 Name: Anonymous 2010-06-09 19:14

51 Name: Anonymous 2010-06-09 19:20

52 Name: >> !!50++bKT00Wlp00p 2010-06-10 0:58

53 Name: Anonymous 2010-06-10 4:23

54 Name: Anonymous 2010-06-10 12:07

55 Name: Anonymous 2010-06-11 15:17

56 Name: Anonymous 2010-06-11 16:40

57 Name: Anonymous 2010-06-11 18:27

58 Name: Anonymous 2010-06-17 19:44

59 Name: Anonymous 2010-06-17 19:46

60 Name: Anonymous 2010-06-17 19:52

61 Name: Anonymous 2010-06-17 20:43

62 Name: Anonymous 2010-06-18 0:04

63 Name: Anonymous 2010-06-18 1:13

65 Name: Anonymous 2010-12-21 18:58

66 Name: Anonymous 2011-01-31 20:38