[Question]
  [
# "Fit Numbers"
Sam has a "brilliant" idea for compression! Can you help?
---
Here is a rundown of Sam's compression scheme. First take in a base 10 representation of any natural number strictly smaller than 2^16, and write it as a binary string without any leading zeros.
```
1 -> 1
9 -> 1001
15 ->1111
13 ->1101
16 -> 10000
17 -> 10001
65535 -> 111111111111111
```
Now replace any group of one or more zeros with a single zero. This is because the number has gotten leaner. Your binary string now will look like this.
```
1 -> 1 -> 1
9 -> 1001 -> 101
15 ->1111 -> 1111
13 ->1101 -> 1101
16 -> 10000 -> 10
17 -> 10001 -> 101
65535 -> 111111111111111 -> 111111111111111
```
Now you convert the binary string back to a base 10 representation, and output it in any acceptable format. Here are your test cases. The first integer represents an input, and the last integer represents an output. Note that some numbers do not change, and thus can be called "fit"
```
1 -> 1 -> 1 -> 1
9 -> 1001 -> 101 -> 5
15 ->1111 -> 1111 -> 15
13 ->1101 -> 1101 -> 13
16 -> 10000 -> 10 -> 2
17 -> 10001 -> 101 -> 5
65535 -> 1111111111111111 -> 1111111111111111 -> 65535
65000 -> 1111110111101000 -> 11111101111010 -> 16250
```
---
You may use any language, but please note that Sam hates standard loopholes. This is code golf so the code can be as short as possible to make room for the "compressed" numbers".
---
Note:This is NOT an acceptable compression scheme. Using this will promptly get you fired.
---
Citation-Needed: I do not take credit for this concept. This comes from @Conor O' Brien's blog [here](http://cergos.blogspot.com/2016/02/fitbits.html) see this OEIS of fit numbers. <https://oeis.org/A090078>
  
[Answer]
# Bash + GNU utilities, 27
```
dc -e2o?p|tr -s 0|dc -e2i?p
```
Input read from STDIN.
[Answer]
## [05AB1E](https://github.com/Adriandmen/05AB1E), ~~8~~ 6 bytes
```
b00¬:C
```
**Explanation**
```
b        # convert input to binary
 00¬:    # replace 00 with 0 while possible
     C   # convert to int
```
[Try it online](http://05ab1e.tryitonline.net/#code=YjAwwqw6Qw&input=NjUwMDA)
Saved 2 bytes thanks to [Adnan](https://codegolf.stackexchange.com/users/34388/adnan)
[Answer]
## JavaScript (ES6), 41 bytes
```
n=>+`0b${n.toString(2).replace(/0+/g,0)}`
```
[Answer]
## [Jellyfish](https://github.com/iatorm/jellyfish), 20 bytes
```
p
d
# S
,1
*
\dbi
 2
```
[Try it online!](http://jellyfish.tryitonline.net/#code=cApkCiMgUwosMQoqClxkYmkKIDI&input=MTc)
## Explanation
* `i` is input.
* `b` converts it to binary (list of digits)
* `\d` with arguments `2` and the digit list applies `d` (binary digits to number) to every length-2 substring of the digit list.
* `*` takes signum of the results: 00 goes to 0, everything else to 1.
* `,1` tacks a 1 to the end, so the last digit is not lost.
* `# S` selects from `bi` those digits which have a 1 on the list computed above: those that are not the left halves of 00.
* `d` converts back to number, and `p` prints the result.
[Answer]
## Python 2, 36 bytes
```
f=lambda n:n and f(n/2)<<(n%4>0)|n%2
```
A direct recursive implementation with no base conversion built-ins or string operations. Less golfed:
```
f=lambda n:n and[f(n/2),n%2+2*f(n/2)][n%4>0]
```
When `n` is a multiple of 4, it ends in two 0's in binary, so we cut one by floor-dividing by 2. Otherwise, we split `n` into `(n%2) + 2*(n/2)`, leave the last binary digit `n%2` alone, and recurse on the other digits `n/2`.
[Answer]
# Bash (sed + bc), ~~60~~ ~~55~~ 43 bytes
```
echo $[2#`bc<<<obase=2\;$1|sed s/00\*/0/g`]
```
edit:
1. changed `sed -E 's/0+` to `sed 's/00*` and changed echo and pipe used to pass the value to bc with `<<<`.
2. Brilliant suggestion by @Digital Trauma!
example:
```
$ bash script.sh 65000
16250
$ bash script.sh 15
15
$ bash script.sh 9
5
```
[Answer]
# [Perl 6](http://perl6.org), ~~31~~ 27 bytes
```
~~{:2(.base(2).subst(:g,/0+/,0))}~~
{:2(.base(2)~~{S:g/0+/0/})}
```
## Explanation:
```
-> $_ {
  # convert from base 2
  :2(
    # convert to base 2
    $_.base(2)
    # substitute
    .subst(
      :global,
      / 0+ /,  # all substrings made of 0s
      '0'      # with one 0
    )
  )
}
```
## Example:
```
my &fit-compress = {:2(.base(2)~~{S:g/0+/0/})}
say fit-compress 1;     # 1
say fit-compress 9;     # 5
say fit-compress 15;    # 15
say fit-compress 13;    # 13
say fit-compress 16;    # 2
say fit-compress 17;    # 5
say fit-compress 65535; # 65535
say fit-compress 65000; # 16250
# number created with ｢:2( [~] <0 1>.roll: 256 )｣
say fit-compress 80794946326210692074631955353531749442835289622757526957697718534769445507500
# 4240335298301026395935723255481812004519990428936918
```
[Answer]
# MATL, ~~11~~ ~~9~~ 8 bytes
```
BFFOZtXB
```
This version works only in MATLAB since `strrep` in MATLAB can handle logical inputs. Here is a version that will work in Octave (9 bytes) (and thus the online interpreter) which explicitly casts the logical inputs to type `double`.
[**Try it online**](http://matl.tryitonline.net/#code=Qm9GRk9adFhC&input=OQ)
**Explanation**
```
    % Implicitly grab input
B   % Convert decimal to binary
FF  % Create the array [0 0]
O   % Number literal
Zt  % Replaces all [0 0] with [0] (will replace any number of 0's with 0)
XB  % Convert binary to decimal
    % Implicitly display
```
[Answer]
# Python 3, ~~55~~, 50 bytes.
Saved 4 bytes thanks to Sp3000.
Pretty straightforward solution.
```
import re
f=lambda x:eval(re.sub('0+','0',bin(x)))
```
[Answer]
# Ruby, ~~35~~ 31 bytes
-2 bytes thanks to @Doorknob
```
->n{eval ("0b%b"%n).squeeze ?0}
```
See it on repl.it: <https://repl.it/CnnQ/2>
[Answer]
## Javascript (ES6), 40 bytes
```
n=>'0b'+n.toString(2).replace(/0+/g,0)-0
```
[Answer]
## Actually, 14 bytes
```
├`'0;;+(Æ`Y2@¿
```
[Try it online!](http://actually.tryitonline.net/#code=4pScYCcwOzsrKMOGYFkyQMK_&input=NjUwMDA)
Explanation:
```
├`'0;;+(Æ`Y2@¿
├               bin(input) (automatically discards leading zeroes)
 `'0;;+(Æ`Y     call this function until the output stops changing:
  '0;;+           push "0", "00"
       (Æ         replace "00" with "0" in binary string
           2@¿  convert from binary to decimal
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~13~~ 7 bytes
**6 bytes thanks to Zgarb for [his algorithm](https://codegolf.stackexchange.com/a/90083/48934).**
```
~~BŒgµL\*x@Ḣµ€FḄ~~
BŒgḄBFḄ
```
[Try it online!](http://jelly.tryitonline.net/#code=QsWSZ-G4hEJG4biE&input=&args=NjUwMDA)
[Answer]
## PHP, 53 51 Bytes
```
<?=bindec(preg_replace("/0+/",0,decbin($argv[1])));
```
Takes an argument from the console.
## Thanks to:
@manatwork replace "0" with 0
[Answer]
## Perl, 38 + 1 (`-p`) = 39 bytes
```
$_=oct"0b".sprintf("%b",$_)=~s/0+/0/gr
```
Needs `-p` flag to run (I added `-l` flag to make it more readable, but it's not needed otherwise) :
```
perl -plE '$_=oct"0b".sprintf("%b",$_)=~s/0+/0/gr' <<< "1
9
15
13
16
17
65535
65000"
```
Note much to say about the code : it converts the number into binary (`sprintf"%b"`), then replaces blocs of zeros by just one zero, and converts the result into decimal (`oct"0b".`).
[Answer]
## C#, ~~112~~ 91 bytes
```
int x(int x)=>Convert.ToInt32(Rege‌​x.Replace(Convert.ToS‌​tring(x,2),"0+","0"),2);
```
-8 bytes thanks to TuukkaX
[Answer]
# Java, 75
```
int f(Integer x){return x.valueOf(x.toString(x,2).replaceAll("0+","0"),2);}
```
Test program:
```
public class Fit {
    int f(Integer x){return x.valueOf(x.toString(x,2).replaceAll("0+","0"),2);}
    public static void main(final String... args) {
        final Fit x = new Fit();
        System.out.println(x.f(65000));
    }
}
```
[Answer]
# [PARI/GP](http://pari.math.u-bordeaux.fr/), ~~54~~ 43 bytes
```
n->fold((a,b)->a+if(b,a+1,a%2,a),binary(n))
```
[Answer]
# C, 37 bytes
```
f(x){return x?f(x/2)<<!!(x%4)|x&1:0;}
```
[Answer]
## PowerShell v2+, 69 bytes
```
[convert]::ToInt32(([convert]::ToString($args[0],2)-replace'0+',0),2)
```
(*[feature-request](/questions/tagged/feature-request "show questions tagged 'feature-request'")A shorter way to convert to/from binary in PowerShell*)
Takes input `$args[0]`, uses the .NET built-in `[convert]::ToString(int,base)` to convert the input integer into a binary base string. That's filtered through the `-replace` to strip out any runs of one-or-more-zeros to just `0`. That resultant string is sent back through the other direction via `[convert]::ToInt32(string,base)` to turn the binary back into an integer. That integer is left on the pipeline and output is implicit.
### Test Cases
```
PS C:\Tools\Scripts\golfing> 1,9,15,13,16,17,65535,65000|%{"$_ -> " +(.\output-fit-number.ps1 $_)}
1 -> 1
9 -> 5
15 -> 15
13 -> 13
16 -> 2
17 -> 5
65535 -> 65535
65000 -> 16250
```
[Answer]
# Reference Implementation in [S.I.L.O.S](https://esolangs.org/wiki/S.I.L.O.S) "only" 417 bytes
Golfed 
```
readIO :
i + 1
I = i
z = 1 
n = 32
b = n
z = 1
n = b
lbla
n - 1
GOSUB p
j = i
j - p
if j b
if z c
z = 1
GOTO e
lblc
b - 1
if n a
GOTO f
lblb
z = 0
A = a
A + 1000
set A 1
i - p
lble
a + 1
if n a
lblf
q = 1000
e = q
e + b
i = 0
lbl>
d = q
d - e
if d ?
n = b
n - i
GOSUB p
g = get q
g * p
o + g
i + 1
q + 1
GOTO >
lbl?
o / 2
printInt o
GOTO z
funcp
p = 1
Z = n
lblQ
if Z C
GOTO D
lblC
Z - 1
p * 2
GOTO Q
lblD
return
lblz
```
Here is the reference implementation fully ungolfed. As a bonus feature it outputs the steps needed to come to an answer. 
```
/**
*Reference Implementation in the high quality S.I.L.O.S language.
*/
readIO Enter a number to "compress"
//some declarations
i + 1
I = i
z = 1 
//the above is a flag which shows whether or not a zero was last outputted
n = 32
b = n
//maximum number of input bits
printLine Original Binary
lblbinLoop
n - 1
GOSUB pow
j = I
j - p
if j printOne
if z ENDLOOP
print 0
GOTO ENDLOOP
lblprintOne
z = 0
print 1
I - p
lblENDLOOP
if n binLoop
printLine  
printLine Binary "Compressed"
z = 1
n = b
lbltopA
n - 1
GOSUB pow
j = i
j - p
if j printAOne
if z DontPrint
z = 1
print 0
GOTO ENDLOOPA
lblDontPrint
b - 1
if n topA
GOTO endOfBin
lblprintAOne
z = 0
print 1
A = a
A + 1000
set A 1
i - p
lblENDLOOPA
a + 1
if n topA
lblendOfBin
printLine  
printLine -----------
printLine Base 10 Output
print Out Bits:
printInt b
q = 1000
e = q
e + b
i = 0
lblOutputDec
d = q
d - e
if d DONE
n = b
n - i
GOSUB pow
g = get q
g * p
o + g
i + 1
q + 1
GOTO OutputDec
lblDONE
printLine
printLine ---------
o / 2
printInt o
GOTO funcs
//function declarations must be wrapped in gotoes to avoid the interpreter from complaining (breaking)
/**
*This will store the nth power of two in the "p" variable
*/
funcpow
p = 1
Z = n
lbltop
if Z continue
GOTO end
lblcontinue
Z - 1
p * 2
GOTO top
lblend
return
lblfuncs
```
By request the transpilation has been deleted. Feel free to view the edit history to recover it, otherwise go to [this repo](https://github.com/rjhunjhunwala/S.I.L.O.S) for an interpreter.
Sample output for 65000
```
Enter a number to "compress"
65000
Original Binary
1111110111101000 
Binary "Compressed"
11111101111010 
-----------
Base 10 Output
Out Bits:14
---------
16250
```
[Answer]
# Pyth, 12
```
i:.BQ"0+"\02
```
[Online.](https://pyth.herokuapp.com/?code=i%3A.BQ%220%2B%22%5C02&input=65000&test_suite=1&test_suite_input=1%0A9%0A15%0A13%0A16%0A17%0A65535%0A65000&debug=0)
```
  .BQ            # Convert input from base 10 to base 2
 :   "0+"\0      # Replace multiple zeroes with single zero
i          2     # Convert back from base 2 to base 10
```
[Answer]
# [Retina](https://github.com/m-ender/retina), 30 bytes
```
.+
$*1;
+`(1+)\1
$1;
1;
1
;+
0
```
[Try it online!](http://retina.tryitonline.net/#code=LisKJCoxOworYCgxKylcMQokMTsKMTsKMQo7Kwow&input=NjUwMDA)
And here I thought Retina would be amongst the first answers...
[Answer]
# Java, ~~152~~ ~~143~~ 138 bytes
```
interface C{static void main(String[]b){Integer i=0;System.out.print(i.parseInt(i.toString(i.parseInt(b[0]),2).replaceAll("0+","0"),2));}}
```
* 9 bytes less thanks to @RohanJhunjhunwala. I prefer to keep it as a fully functioning program with main and the like. However, of course it can be golfed more otherwise.
* 5 bytes less thanks to @LeakyNun's suggestions.
[Answer]
# [Dyalog APL](http://goo.gl/9KrKoM), 19 [bytes](http://meta.codegolf.stackexchange.com/a/9429/43319)
```
{2⊥⍵/⍨~0 0⍷⍵}2∘⊥⍣¯1
```
[TryAPL online!](http://tryapl.org/?a=f%u2190%7B2%u22A5%u2375/%u2368%7E0%200%u2377%u2375%7D2%u2218%u22A5%u2363%AF1%20%u22C4%20f%A81%209%2015%2013%2016%2017%2065535%2065000&run)
**This function is really an "atop" of two functions, the first function is:**
`2∘⊥⍣¯1` the *inverse* of binary-*to*-decimal conversion, i.e. binary-*from*-decimal conversion  
 *two* `2` *is bound* `∘` to *-to-decimal* `⊥`  
 *repeat* the operation `⍣` *negative one* time `¯1` (i.e. once, but inverted)
**In the second function, the above's binary result is represented by** `⍵`**:**
`{2⊥⍵/⍨~0 0⍷⍵}`  
 `0 0⍷⍵` Boolean for where {0, 0} begins in ⍵  
 `~` Boolean negation, so now we have ᴛʀᴜᴇ everywhere but at non-first zeros in zero-runs  
 `⍵/⍨` use that to filter ⍵, so this removes our unwanted zeros  
 `2⊥` convert binary-to-decimal
[Answer]
# TSQL, 143 bytes
Not using build ins to convert from and to binary.
Golfed:
```
DECLARE @i INT=65000
,@ CHAR(99)=''WHILE @i>0SELECT @=REPLACE(LEFT(@i%2,1)+@,'00',0),@i/=2WHILE @>''SELECT @i+=LEFT(@,1)*POWER(2,LEN(@)-1),@=STUFF(@,1,1,'')PRINT @i
```
Ungolfed:
```
DECLARE @i INT=65000
,@ CHAR(99)=''
WHILE @i>0
  SELECT @=REPLACE(LEFT(@i%2,1)+@,'00',0),@i/=2
WHILE @>''
  SELECT @i+=LEFT(@,1)*POWER(2,LEN(@)-1),@=STUFF(@,1,1,'')
PRINT @i
```
**[Fiddle](https://data.stackexchange.com/stackoverflow/query/525494/output-fit-numbers)**
[Answer]
# CJam, 16
```
q~2b1+0a%0a*);2b
```
[Try it online](http://cjam.aditsu.net/#code=q~2b1%2B0a%250a*)%3B2b&input=65000)
It's quite long due to lack of regex.
**Explanation:**
```
q~     read and evaluate the input number
2b     convert to base 2 (array of 1s and 0s)
1+     append a 1 to deal with trailing zeros
0a%    split by [0], dropping empty pieces; only chunks of 1s are left
0a*    join by [0]
);     discard the 1 we appended before
2b     convert back from base 2
```
[Answer]
# Java, 64 bytes
```
i->{return i.parseInt(i.toString(i,2).replaceAll("0+","0"),2);};
```
# Test Program
```
public static void main(String[] args) {
    Function<Integer, Integer> function = i -> {
        return i.parseInt(i.toString(i, 2).replaceAll("0+", "0"), 2);
    };
    System.out.println(function.apply(1)); // 1
    System.out.println(function.apply(9)); // 5
    System.out.println(function.apply(15)); // 15
    System.out.println(function.apply(13)); // 13
    System.out.println(function.apply(16)); // 2
    System.out.println(function.apply(17)); // 5
    System.out.println(function.apply(65535)); // 65535
}
```
[Answer]
# [CJam](https://sourceforge.net/projects/cjam/), 23 bytes
```
ri2be`{_:g:>{:g}&}%e~2b
```
[**Try it online!**](http://cjam.tryitonline.net/#code=cmkyYmVge186Zzo-ezpnfSZ9JWV-MmI&input=MTc)
### Explanation
```
ri          e# Read input as an integer
2b          e# Convert to binary
e`          e# Run-length encoding. Gives a nested (2D) array with run-lengths 
            e# and binary digits
{           e# This block is mapped over the outer array, i.e. is applied to
            e# each inner array
   _        e#   Duplicate the inner array
  :g        e#   Signum of each element of inner array
  :>        e#   This gives true if second element (digit) is false and first
            e#   element (run-length) is not zero. If so, we need to set that
            e#   run-length to 1
  {:g}&     e#   If that's the case, apply signum to original copy of inner
            e#   array, to make run-length 1
}%          e# End block which is mapped over the outer array
e~          e# Run-length decoding
2b          e# Convert from binary. Implicitly display
```
[Answer]
### Ruby, 37 35 bytes
Saved two bytes thanks to manatwork.
```
->a{a.to_s(2).gsub(/0+/,?0).to_i 2}
```
The naive approach. (:
]