[S S S N
_Push_0][S N
S _Duplicate_0][S N
S _Duplicate_0][T N
T T _Read_STDIN_as_integer][T T T _Retrieve][N
S S N
_Create_Label_LOOP][S N
S _Duplicate][N
T S S N
_If_0_jump_to_Label_PRINT][S S S T S N
_Push_2][T S T S _Integer_division][S N
T _Swap_top_two][S S S T N
_Push_1][T S S S _Add][S N
T _Swap_top_two][N
S N
N
_Jump_to_Label_LOOP][N
S S S N
_Create_Label_PRINT][S N
N
_Discard_top][T N
S T _Print_integer]
Letters S
(space), T
(tab), and N
(new-line) added as highlighting only.
[..._some_action]
added as explanation only.
Try it online (with raw spaces, tabs and new-lines only).
Explanation in pseudo-code:
Integer i = STDIN as integer
Integer r = 0
Start LOOP:
if i is 0:
Call function PRINT_AND_EXIT
i = i integer-divided by 2
r = r + 1
Go to next iteration of LOOP
function PRINT_AND_EXIT:
Print r as integer
Exit with error
Example run (n=16
):
Command Explanation Stack HEAP STDIN STDOUT STDERR
SSSN Push 0 [0]
SNS Duplicate top (0) [0,0]
SNS Duplicate top (0) [0,0,0]
TNTT Read STDIN as integer [0,0] {0:16} 16
TTT Retrieve [0,16] {0:16}
NSSN Create Label_LOOP [0,16] {0:16}
SNS Duplicate top (16) [0,16,16] {0:16}
NTSSN If 0: Jump to Label_PRINT [0,16] {0:16}
SSSTSN Push 2 [0,16,2] {0:16}
TSTS Integer-divide (16/2) [0,8] {0:16}
SNT Swap top two [8,0] {0:16}
SSSTN Push 1 [8,0,1] {0:16}
TSSS Add (0+1) [8,1] {0:16}
SNT Swap top two [1,8] {0:16}
NSNN Jump to Label_LOOP [1,8] {0:16}
SNS Duplicate top (8) [1,8,8] {0:16}
NTSSN If 0: Jump to Label_PRINT [1,8] {0:16}
SSSTSN Push 2 [1,8,2] {0:16}
TSTS Integer-divide (8/2) [1,4] {0:16}
SNT Swap top two [4,1] {0:16}
SSSTN Push 1 [4,1,1] {0:16}
TSSS Add (1+1) [4,2] {0:16}
SNT Swap top two [2,4] {0:16}
NSNN Jump to Label_LOOP [2,4] {0:16}
SNS Duplicate top (4) [2,4,4] {0:16}
NTSSN If 0: Jump to Label_PRINT [2,4] {0:16}
SSSTSN Push 2 [2,4,2] {0:16}
TSTS Integer-divide (4/2) [2,2] {0:16}
SNT Swap top two [2,2] {0:16}
SSSTN Push 1 [2,2,1] {0:16}
TSSS Add (2+1) [2,3] {0:16}
SNT Swap top two [3,2] {0:16}
NSNN Jump to Label_LOOP [3,2] {0:16}
SNS Duplicate top (2) [3,2,2] {0:16}
NTSSN If 0: Jump to Label_PRINT [3,2] {0:16}
SSSTSN Push 2 [3,2,2] {0:16}
TSTS Integer-divide (2/2) [3,1] {0:16}
SNT Swap top two [1,3] {0:16}
SSSTN Push 1 [1,3,1] {0:16}
TSSS Add (3+1) [1,4] {0:16}
SNT Swap top two [4,1] {0:16}
NSNN Jump to Label_LOOP [4,1] {0:16}
SNS Duplicate top (1) [4,1,1] {0:16}
NTSSN If 0: Jump to Label_PRINT [4,1] {0:16}
SSSTSN Push 2 [4,1,2] {0:16}
TSTS Integer-divide (1/2) [4,0] {0:16}
SNT Swap top two [0,4] {0:16}
SSSTN Push 1 [0,4,1] {0:16}
TSSS Add (4+1) [0,5] {0:16}
SNT Swap top two [5,0] {0:16}
NSNN Jump to Label_LOOP [5,0] {0:16}
SNS Duplicate top (0) [5,0,0] {0:16}
NTSSN If 0: Jump to Label_PRINT [5,0] {0:16}
NSSSN Create Label_PRINT [5,0] {0:16}
SNN Discard top [5] {0:16}
TNST Print as integer [] {0:16} 5
error
Program stops with an error: No exit found.
2This is the ceiling of the base-2 logarithm. – orlp – 2016-12-27T16:51:22.520
23@orlp It actually is
floor(log2(num))+1
– user41805 – 2016-12-27T16:52:37.7572@KritixiLithos Right. – orlp – 2016-12-27T18:46:30.903
@KritixiLithos What's an example for when
ceil(log2(num)) != floor(log2(num)) + 1
? I'm racking my brain trying to figure out why the distinction is important. – Brian J – 2016-12-27T20:21:38.5633Nevermind, just realized that the distinct is important when
num
is a power of two. – Brian J – 2016-12-27T20:22:47.37711
This is a trivial challenge with a lot of trivial solutions. There are however some non-trivial solutions too. To voters: Please read the first sentence of this meta post before upvoting builtin functions. (humbly taken from this comment)
– user41805 – 2016-12-28T08:23:53.787Am I wrong that you need 32 bits to represent any 32-bit integer? If I want to represent 1 in binary, I need 31 0's and one 1. I can't store "11" as "11" in memory. – MatthewRock – 2016-12-29T13:23:47.867
@MatthewRock Technically, you could store
1
in one bit (1
). With fixed-width integers, yes, that would take up 32 bits (assuming 32-bit word size), but 31 of those bits are redundant (leading zeroes). – Mego – 2016-12-30T23:23:01.580Just out of curiosity, how many bits does it take to store zero (0)? – Octopus – 2017-01-20T23:17:04.387
@Octopus 1 bit. – Bassdrop Cumberwubwubwub – 2017-02-08T13:10:36.257
@BrianJ But this:
ceil(log2(num+1)) == floor(log2(num)) + 1
– ბიმო – 2017-07-19T17:04:24.407For 64 bit (without the +1). – user202729 – 2018-12-10T13:31:28.553