I like to golf in dc, but I'm sometimes frustrated because dc doesn't have bitwise operations.

Challenge

Provide four named functions which implement the equivalent of the c bitwise operations &, |, ~ and ^ (bitwise AND, OR, NOT and XOR). Each function will take two operands (~ takes only one) which are at least 32-bit unsigned integers. Each function will return an unsigned integer of the same bit-width as the operands.

Restriction

You may only use operations that are supported by dc. These are:

  • + - * / Arithmetic addition, subtraction, multiplication and division
  • ~ modulo (or divmod if your language supports it)
  • ^ exponentiation
  • | modular exponentiation
  • v square root
  • > >= == != <= < standard equality/inequality operators
  • >> << bit shift operators. dc doesn't have these, but since they are trivially implemented in terms of division/multiplication by powers of 2, then I will allow these.

Control structures in dc my be clumsily built using (recursive) macros and (in)equality operations. You may use whatever built-in control structures your language has.

You may also use logical operators && || !, even though these aren't directly available in dc.

You must not use the bitwise operators &, |, ~ and ^ or any functions that trivially implement them.

In addition you must not use built-in base-conversion-of-string operators or functions.


Please also consider providing a test program or online compiler snippet (not included in the golf score) to help verify your answer.

  • Can we implement one function that takes the desired operation as a parameter? Also, can we integer-divide by 2 as a stand-in for bit-shift? – xnor Apr 3 '15 at 0:44
  • @xnor You must provide 4 public functions that implement each of the four operators. You may also have common/helper private methods/functions that are called by all four public functions, but these will all need to be included in the golf score. – Digital Trauma Apr 3 '15 at 0:48
  • 6
    @xnor You and you only must also implement the xnor operator ;-) – Digital Trauma Apr 3 '15 at 0:49
  • Can I produce a list of four anonymous functions? – xnor Apr 3 '15 at 7:14
  • @MariaTidalTug What's the effective difference between returning a list of four functions and manually selecting and applying one (as xnor suggested) versus having one function that accepts the selection parameter and performs the selection itself (as wolfhammer answered)? They both seem to similarly undermine the point of having four named functions, as they offload code size onto the user code. I'd even argue that the former undermines it more, as the user code is probably more complex in that case than in the latter case. – Runer112 Apr 3 '15 at 14:43

C, 134

The C preprocessor is pretty fun to abuse. Basically this macro defines the 3 functions, a, o, and x, for and, or, and xor respectively. The only difference in the algorithm for these operations is the criteria for setting the bit in the result.

not is the function n.

#define f(n,c)n(a,b){for(r=0,i=31;i+1;--i)if(((a>>i)%2+(b>>i)%2)c)r+=1<<i;return r;}
i,r;n(a){return 0xffffffff-a;}f(a,/2)f(o,)f(x,%2)

Tester program (takes a long time, I didn't spend any time optimizing it at all, but it does test every test case possible, beside MAX_INT related ones):

#define m_assert(expected, condition, actual)\
    if(!((expected) condition (actual)))\
        printf("assert fail @ line %i, expected: %x, actual %x, condition "#condition"\n", __LINE__, expected, actual);

int main()  {
    unsigned int j,k;
    for(j=0; j<0xffff; ++j)    {
        m_assert(~j, ==, n(j));
        for(k=0; k<0xffff; ++k)    {
            m_assert(j & k, ==, a(j,k));
            m_assert(j | k, ==, o(j,k));
            m_assert(j ^ k, ==, x(j,k));
        }
    }
  • 1
    oops. forgot about that. fixed that now. – pseudonym117 Apr 3 '15 at 16:49

ised 76 bytes

ised also doesn't have bitwise operations - usually annoying, but now welcome, because we really need to implement them.

Functions will be stored in numbered memory slots (no verbose names).

Conversion to and from binary:

@5{:x/2^[32]%2:};
@6{:x@:2^[32]:};

NOT could be @1{:$6::{1-$5::x}:} but it's obviously easier to just subtract:

@1{:2^32-x-1:};

OR:

@2{:$6::{$5::{x_0}:+$5::{x_1}>0}:};

AND:

@3{:$6::{$5::{x_0}:*$5::{x_1}}:};

XOR:

@4{:$6::{$5::{x_0}:<>$5::{x_1}}:};

This would bring us to 156 bytes (with newlines and semicolons). A test code would just be (NOT, OR, AND, XOR in succession, found under names $1,$2,$3,$4):

> $1::{6}
4294967289
> $2::{12 11}
15
> $3::{12 11}
8
> $4::{12 11}
7

But of course OR and NOT are all we really need and things can be simplified:

@1{:2^32-x-1:};
@2{:@+{2^U{?{$5::x}%32}}:};
@3{:${1 2 1}::x:};
@4{:$3::{$2::x${1 2}::x}:};
@5{:x/2^[32]%2:};

That's 109 characters. When newlines and semicolons are skipped, and with a bit more golfing, we have 76 characters:

@3{@1{:2^32-x-1:}@2{:@+{2^U{?{x/2^[32]%2}%32}}:}$1}@4{{:$2::x${1 2}::x:}$3};

Nim (537)(490)

Nim Compiler 0.10.2

I've been looking for a reason to learn nim so here we go.

For code golf, I have leveraged variable parameters and implicit returns. The variable parameters, per the documentation are less stack efficient. Personally, I find the implicit returns harder to read and would probably only use them in trivial procedures.

As for the algorithms, they are simple enough. For all operations except NOT, we compare each bit and manually compare them to our expected truth table. Set each bit as needed along the way in our output variable. In Nim, result is the implicit return value.

I wasn't sure if we were allowed to use built-in OR and AND for asserting two boolean conditions so the notZero procedure was put in their place.

proc s(x, y, b: var int)=
  x = x div 2
  y = y div 2
  b *= 2

proc n(x: var int): int =
  return -(x+1)

proc a(x, y: var int): int =
  var b = 1
  while x > 0 and y > 0:
    if (x mod 2  + y mod 2) == 2:
      result += b

    s(x,y,b)

proc o(x, y: var int): int =
  var b = 1
  while x + y > 0:
    if (x mod 2 + y mod 2) >= 1:
      result += b

    s(x,y,b)

proc r(x, y: var int): int =
  var b = 1
  while x + y > 0:
    if (x mod 2 + y mod 2) == 1:
      result += b

    s(x,y,b)

Still looking for a better method...

Here is the non-squished version plus full test harness to run on your own machine.
If you just want to run a couple of inputs, here is test case lite.

  • @MariaTidalTug thanks for clarifying! – cory.todd Apr 3 '15 at 5:57
  • I can't reproduce that. Is your calculator in base-16 mode? – cory.todd Apr 3 '15 at 17:36
  • I added a test harness similar to pseudonym117's. – cory.todd Apr 3 '15 at 17:54

CJam, 71 bytes

{:F;0{:R;2md@2md@+F~!2I#*R+}64fI\;\;}:B{"2-"B}:A{'!B}:O{0SB}:N{'(B}:X];

Explanation

"B : UInt64 UInt64 String -> UInt64
 Computes a bitwise operation on the two given unsigned integers. The operation
 is defined by the logical inverse of the result of evaluating the given string
 given the sum of two input bits.";
{
  :F;             "Save the operation string.";
  0               "Initialize the result to 0.";
  {               "For I from 0 through 63:";
    :R;             "Save the result.";
    2md@2md@        "Divide each input by 2 and collect the remainders as the
                     next pair of bits to process.";
    +F~!            "Compute the logical inverse of the result of evaluating
                     the operation string given the sum of the two bits.";
    2I#*            "Adjust the resulting bit to be in the correct output
                     position by multiplying it by 2^I.";
    R+              "Add the location-adjusted bit to the result.";
  }64fI
  \;\;            "Clean up.";
}:B

"A : UInt64 UInt64 -> UInt64
 Computes the bitwise AND of the two given unsigned integers.
 This is done by passing the inputs along to B with an operation such that:
   bit_out = !((bit_in_1 + bit_in_2) - 2)";
{"2-"B}:A

"O : UInt64 UInt64 -> UInt64
 Computes the bitwise OR of the two given unsigned integers.
 This is done by passing the inputs along to B with an operation such that:
   bit_out = !(!(bit_in_1 + bit_in_2))";
{'!B}:O

"N : UInt64 -> UInt64
 Computes the bitwise NOT of the given unsigned integer.
 This is done by passing the input and 0 along to B with an operation such that:
   bit_out = !((bit_in + 0))";
{0SB}:N

"X : UInt64 UInt64 -> UInt64
 Computes the bitwise XOR of the two given unsigned integers.
 This is done by passing the inputs along to B with an operation such that:
   bit_out = !((bit_in_1 + bit_in_2) - 1)";
{'(B}:X

];              "Clean up.";

Test suite

This code tests runs of each of my and, or, not, and xor functions 100 times with uniformly-distributed 64-bit unsigned inputs and compares the result with that produced by the built-in operator. Due to gratuitous use of the eval operator, it's quite slow and may take up to about a minute with the online interpreter. But if all goes well, execution should end with no output, because any discrepancies found are printed.

N:L;
{:F;0{:R;2md@2md@+F~!2I#*R+}64fI\;\;}:B{"2-"B}:A{'!B}:O{0SB}:N{'(B}:X];
{;Y32#__mr*\mr+}2e2%2/{~:U;:V;"A&O|X^"2/{[{US@SV" = "UV5$~L}/9$2$={];}{]oLo}?}/"N~"[{U" = "U3$~Y64#(&L}/6$2$={];}{]oLo}?}/

JavaScript 294 267

Was able to shave off a few more bytes with @AlexA.'s and @kennytm's suggestions.

Functions:

B=(n,m,t)=>{for(var p=4294967296,y=0;p>=1;p/=2)y+=t=='x'&&(n>=p||m>=p)&& !(n>=p&&m>=p)?p:0,y+=t=='a'&&n>=p&&m>=p?p:0,y+=t=='o'&&(n>=p||m>=p)?p:0,n-=n>=p?p:0,m-=m>=p?p:0
return y}
N=(n)=>{return 4294967295-n}
A=(n,m)=>B(n,m,'a')
O=(n,m)=>B(n,m,'o')
X=(n,m)=>B(n,m,'x')

example:

var n = 300;
var m = 256;
console.log(X(n,m) + ", " + (n ^ m));
console.log(O(n,m) + ", " + (n | m));
console.log(A(n,m) + ", " + (n & m));
console.log(N(n) + ", " + (~n>>>0));
console.log(N(m) + ", " + (~m>>>0));

output:

44, 44
300, 300
256, 256
4294966995, 4294966995
4294967039, 4294967039
  • 2
    You need to provide four public functions - one each for AND, OR. NOT and XOR. (You may also have common/helper private methods/functions that are called by all four public functions). Also, you are missing the NOT - probably the easiest of all of these to do – Digital Trauma Apr 3 '15 at 0:46
  • Thanks @AlexA. I've added the bytes and golfed it some more. – wolfhammer Apr 3 '15 at 20:28
  • You can lose the space after for and replace function B(n,m,t) with B=(n,m,t)=>. Likewise for the other functions. – Alex A. Apr 3 '15 at 21:07
  • ① You could use 4*(1<<30) for 4294967296 and -1>>>0 for 4294967295. ② is the var truly necessary here? ③ you could write (n,m)=>B(n,m,'a') instead of (n,m)=>{return B(n,m,'a')} – kennytm Apr 4 '15 at 20:50

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.