Make a function that increments a number using only bitwise, loops, and conditions.
Rules:
All entries must be as per the language spec defined below.
Scoring is not of code length, but of the points for each operation given below.
The entry point is
inc(a)
, for "increment and return a".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):
( ... )
~
/!
(right-to-left)<<
/>>
/>>>
(left-to-right)>
/<
/>=
/<=
(left-to-right)==
/!=
(left-to-right)- Note:
1 == 1 == 1
works out to0 == 1
which is0
.
- Note:
&
(left-to-right)^
(left-to-right)|
(left-to-right)&&
(left-to-right)||
(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 `^`
}
5 Answers 5
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
};
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.
-
\$\begingroup\$ It works when converted to C/C++. Good answer \$\endgroup\$bacchusbeale– bacchusbeale2014年06月22日 09:06:46 +00:00Commented Jun 22, 2014 at 9:06
-
\$\begingroup\$ No. It only returns the incremented value. JS only has pass by reference for primitives. \$\endgroup\$Claudia– Claudia2014年06月23日 02:38:32 +00:00Commented Jun 23, 2014 at 2:38
11 (Works for negatives)
function inc(a) {
for(var b=1;a&b;b<<=1) {
a=a^b;
}
return a^b
}
-
1\$\begingroup\$ How are
for
loops scored? \$\endgroup\$xnor– xnor2014年06月22日 18:36:16 +00:00Commented Jun 22, 2014 at 18:36 -
\$\begingroup\$ @xnor I treated them as
1 + (score for code in brackets)
. \$\endgroup\$kitcar2000– kitcar20002014年06月23日 17:50:10 +00:00Commented Jun 23, 2014 at 17:50
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
}
-
\$\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– Tal2014年06月22日 09:04:36 +00:00Commented Jun 22, 2014 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– Paul R2014年06月22日 09:14:40 +00:00Commented Jun 22, 2014 at 9:14
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
}
-
\$\begingroup\$ It is 13. I clarified...apparently that didn't get caught in the Sandbox phase \$\endgroup\$Claudia– Claudia2014年06月23日 02:40:32 +00:00Commented Jun 23, 2014 at 2:40
Explore related questions
See similar questions with these tags.
javascript
tag. Note also that language-specific challenges are rather lame, especially given that many languages share this same set of operators. \$\endgroup\$