3
\$\begingroup\$

Make a function that increments a number using only bitwise, loops, and conditions.

Rules:

  1. All entries must be as per the language spec defined below.

  2. Scoring is not of code length, but of the points for each operation given below.

  3. The entry point is inc(a), for "increment and return a".

  4. Lowest score wins.

See the example to help with scoring.

Language Spec (strict JS subset):

All input is assumed to be signed 32-bit integers, with input being in the range [-231+1, 231-2] (interval notation), with the upper bound to give room for the increment. All output is assumed to be within the range [-231+2, 231-1].

Whitespace is never syntactically significant beyond separating literals, keywords, and newline-ended comments. Booleans for conditions can and may be implicitly converted to integers, with 1 == true and 0 == false. All variables are passed by value (as they are all primitives).

Cost is given for each element, with "per use" implied.

Comments: (0 pts)

/* like this */
// or this

Numeric or variable literal: (0 pts)

i, someVariable, 2, etc.

Boolean literal: (0 pts)

true  // == 1, implicit conversion
false // == 0, implicit conversion
  • Note: Integer to boolean conversion is as follows (in pseudocode):

    if 0: true
    else: false
    

Grouping: (0 pts)

(foo && bar);

Function declaration: (0 pts)

function foo() { ... } // braces required
function bar(a) { ... }

Declare variable: (0 pts)

var a;

Assignment: (1 pt)

var a = 1; // semicolon required to terminate statement
a = 2; // only needs declared once
var b = a;
// b = a = 3; // cannot assign in right side of statement
var c = a << 5;
var d = a ^ (c << 5);

Equality/Inequality: (1 pt)

x == 1; // equality
x != 1; // inequality
x > y; // greater than
x >= y; // greater than or equal to
x < y; // less than
x <= y; // less than or equal to

Logical operators: (1 pt)

  • !a (not)
  • a && b (and, returns 1 if both are true, 0 otherwise)
  • a || b (or, returns 1 if either are true, 0 otherwise)

Bitwise operators: (1 pt)

  • ~a (not)
  • a & b (and)
  • a | b (or)
  • a ^ b (exclusive or)
  • a << b (arithmetic left shift)
  • a >> b (arithmetic right shift)
  • a >>> b (logical right shift)

Augmented assignment: (2 pts)

a &= b; // example

If statement: (condition value + 1 pt)

if (condition) { ... }
if (x == 2) { ... } // worth 2 pts
if (x) { ... } // x is nonzero, worth 1 pt

If-Else statement: (condition value + 2 pts)

if (condition) { ... } else { ... }

While statement: (condition value + 2 pts)

while (condition) { ... }
while (x == 2) { ... } // worth 3 pts
while (x) { ... } // evaluation same as in if, worth 2 pts

Do-While statement: (condition value + 2 pts)

do { ... } while (condition); // semicolon required

Return statement: (number of points for statement on right + 1 pt)

return foo; // semicolon required, worth 1 pt
return a & b; // worth 2 pts

Function call: (number of parameters + 2 pts)

foo(); // worth 2 pts
bar(1, 2) // worth 2 + 2 = 4 pts

Operator precedence (first to last performed):

  1. ( ... )
  2. ~/! (right-to-left)
  3. <</>>/>>> (left-to-right)
  4. >/</>=/<= (left-to-right)
  5. ==/!= (left-to-right)
    • Note: 1 == 1 == 1 works out to 0 == 1 which is 0.
  6. & (left-to-right)
  7. ^ (left-to-right)
  8. | (left-to-right)
  9. && (left-to-right)
  10. || (left-to-right)

Example scoring:

This (ficticious) example would score 14 points. See comments for details.

function inc(a) {
  var b = a; // adds 1 pt for assignment
  if (!a) return 0; // adds 3 pts: 2 for if and 1 for return
  while (a & b) { // adds 3 pts: 2 for while and 1 for `&`
    b >>= a ^ b; // adds 3 pts: 2 for augmented assignment, 1 for `^`
    a = b << 1; // adds 2 pts: 1 for assignment, 1 for `<<`
  }
  return a ^ b; // adds 2 pts: 1 for return, 1 for `^`
}
\$\endgroup\$
  • 4
    \$\begingroup\$ Is there a Javascript-only requirement? If so please make this explicit in the question and add a javascript tag. Note also that language-specific challenges are rather lame, especially given that many languages share this same set of operators. \$\endgroup\$ – Paul R Jun 22 '14 at 9:17
  • 1
    \$\begingroup\$ @PaulR And even if they didn't, I think the wording is good enough the prevent any loopholes with, let's say, J. \$\endgroup\$ – seequ Jun 22 '14 at 10:06
  • \$\begingroup\$ Does this need to work for negatives? Are numbers limited to 32 bits? \$\endgroup\$ – xnor Jun 22 '14 at 17:20
  • \$\begingroup\$ Does JS implicitly cast between Booleans and numbers? \$\endgroup\$ – xnor Jun 22 '14 at 17:22
  • \$\begingroup\$ Yes, but treat them as integers in this context. \$\endgroup\$ – Isiah Meadows Jun 23 '14 at 2:19
4
\$\begingroup\$

10

Works for negative numbers.

function inc(x) 
{ 
    if(x & 1)                       // 1 + 1
        return inc(x >>> 1) << 1;   // 1 + 3 + 1 + 1

    return x | 1;                   // 1 + 1
};
\$\endgroup\$
2
\$\begingroup\$

11 points (also works for negative numbers)

function inc(a) {
  var t = 1;             // 1 pt
  while (a & t) {        // 3 pts
    a &= (~t);           // 3 pts
    t <<= 1;             // 2 pts
  }
  return a|t;            // 2 pts
}

I thought this was supposed to actually increment the number it was called on, but I am not familiar with a way to pass integers by reference in JS.

\$\endgroup\$
  • \$\begingroup\$ It works when converted to C/C++. Good answer \$\endgroup\$ – bacchusbeale Jun 22 '14 at 9:06
  • \$\begingroup\$ No. It only returns the incremented value. JS only has pass by reference for primitives. \$\endgroup\$ – Isiah Meadows Jun 23 '14 at 2:38
2
\$\begingroup\$

11 (Works for negatives)

function inc(a) {
    for(var b=1;a&b;b<<=1) {
        a=a^b;
    }
    return a^b
}
\$\endgroup\$
  • 1
    \$\begingroup\$ How are for loops scored? \$\endgroup\$ – xnor Jun 22 '14 at 18:36
  • \$\begingroup\$ @xnor I treated them as 1 + (score for code in brackets). \$\endgroup\$ – kitcar2000 Jun 23 '14 at 17:50
2
\$\begingroup\$

10 (works for negative numbers)

function inc(a)
{
    var c = 1;                   // 1 
    while (c)                    // 2
    {
        var s = a ^ c;           // 2
        c = (a & c) << 1;        // 3
        a = s;                   // 1
    }
    return a;                    // 1
}
\$\endgroup\$
  • \$\begingroup\$ The question mentions that the language spec you need to use is a JS subset, I understood that as a requirement to use JS... but I don't think there's much of a difference here anyway. \$\endgroup\$ – Tal Jun 22 '14 at 9:04
  • \$\begingroup\$ I've converted it to JS now (I think - I've never used JS before) - I'll also ask the OP to clarify the question. \$\endgroup\$ – Paul R Jun 22 '14 at 9:14
0
\$\begingroup\$

10 (13 if it must work for negative numbers)

function inc(a){
  var m=1;             // 1pts
  while((a & m)==m){   // 4pts
    m=(m<<1)|1;        // 3pts
  }
  return a^m;          // 2pts
}
\$\endgroup\$
  • \$\begingroup\$ It is 13. I clarified...apparently that didn't get caught in the Sandbox phase \$\endgroup\$ – Isiah Meadows Jun 23 '14 at 2:40

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.