DouKaku?beta

challenge ２進数の記述

　コンピューターの原理は2進数だというのに、多くのプログラミング言語で8進数や16進数しか記述できないのは少し変だとは思いませんか？
　そこで、ソース中に２進数を定数として書く方法、またはその代替手段を考えてください。

ある程度の評価基準を示します(できるところまでで構いません)。
・2進数の表示方法は0と1
・桁数は可変長
・コンパイル等の後に最適化等によって定数に変換されることが見込まれる

Cで関数として実装したものを示しておきます。 
1
2
3
4
5
int bin(int b1, int b2, int b3, int b4, int b5, int b6, int b7, int b8){
    return b1<<7 | b2 <<6 | b3<<5 | b4<<4 | b5<<3 | b6<<2 | b7<<1 | b8;
}

int byte = bin(0, 1, 1, 0, 1, 0, 0, 1);
post comment

Posted feedbacks - Nested

Flatten Hidden
Squeak Smalltalk では 2r01101001 という書式で二進数のリテラル記述が可能です。 
1
2r01101001   "=> 105 "

1
2
3
4
5
bin :: [Integer] -> Integer
bin = foldl (\x y -> x * 2 + y) 0

-- Prelude> bin[0, 1, 1, 0, 1, 0, 0, 1]
-- 105

リストで書くのはめんどくさいので。

1
2
3
4
5
6
b :: Integer -> Integer
b 0 = 0
b x = b' x + 2 * b (div x 10)
    where b' x = if odd x then 1 else 0

main = print $ b 01101001  -- 10

Template Haskell を使ってみた。 2ファイルあります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
{- binmain.hs -}

import Bin

main = print $(b 01101001)



{- bin.hs -}

module Bin (b) where

import Language.Haskell.TH

bin :: Integer -> Integer
bin 0 = 0
bin x = bin' x + 2 * bin (div x 10)
    where bin' x = if odd x then 1 else 0

b x = litE $ IntegerL $ bin x

{-
>> ghc --make -fth binmain.hs 
>> ./binmain
105
-
オーソドックスに。C# だとコンパイル時計算って……むりだったような気が……。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
using System;
static class Program {
    static void Main() {
        Console.WriteLine(Bin(01001001));   // 73
        Console.WriteLine(Bin(01101001));   // 105
    }
    static int Bin(uint octet) {
        int digit = 1, bin = 0;
        while(octet != 0) {
            if ((octet % 10) != 0) bin |= digit;
            digit <<= 1;
            octet /= 10;
        }
        return bin;
    }
}
んー。やっぱり C# なら文字列として持ってたほうが良いかな。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
using System;
static class Program {
    static void Main() {
        Console.WriteLine(Bin("01001001"));   // 73
        Console.WriteLine(Bin("01101001"));   // 105
    }
    static int Bin(string num) {
        return Convert.ToInt32(num, 2);
    }
}

リテラルとしての2進数表現は現在ありませんが、以下のように書く事ができます。
(Python3.0では二進数表記も使えます)
1
2
3
4
5
6
i = int('01101001', 2) # 105

# 0,1以外はエラー
i = int('11111112', 2) # ValueError: invalid literal for int() with base 2: '1112'

i = 0b01101001 # python3.0

リテラルで書けます。

1
p 0b01101001  #=> 105

D言語では2進リテラルが使えます。
1
2
3
4
5
6
7
import std.stdio;

int main(){
    writefln("%d", 0b01101001);

    return 0;
}
HSP にはソース中に２進数を定数として書く方法として '0b' や '%' のプレフィックスがあります。 
1
2
mes 0b01101001
mes %01101001

Common Lisp は #b で二進数が書けます。Emacs Lisp, Scheme でも同じ書き方ができます。

1
#b1010 ; => 10

なでしこにはプリプロセスがあるのにマクロがなかったりするので、関数で表現するしかないようです。

1
2
3
4
5
6
BIN("1010")を表示
●BIN(x)
    sとは整数;nとは整数=文字数(x)
    (文字列分解(x))で反復
    　　n=n-1;s=s+(対象*2^n)
    sで戻る

この話題、すでに

でやっちゃっているのですが念のため。

Dan the Perl Monger 

1
2
3
4
# 引数チェックあり
sub bin{ eval  "0b" . join('', grep /^[01]$/, @_)  };
# なし
sub bin{ eval  "0b" . join('',  @_)  };

OCamlもliteralで二進数が書けます。

1
2
# 0b01101001;;
- : int = 105

考え方としては#4565と同じ。

Dan the JavaScripter 

1
2
3
4
5
function bin(){
  var str = '';
  for (var i = 0, l = arguments.length; i < l; i++) str += arguments[i]+0;
  return parseInt(str, 2);
}

2進数のリテラルはありません。

1
Integer.parseInt("1000", 2)

最適化されませんがせっかくなので ruby1.9 で書いてみました。Enumerable によるメソッドチェイン部分だけが 1.9 必要部分です。 

ruby 1.9.0 (2007-11-21 patchlevel 0) [i686-linux]

Ruby ではメソッド呼び出しのカッコを省略できるのですが、文字列リテラルを最初の引数に書く場合にはさらに空白も省略できます (1.8 でも)。 

1
2
3
4
5
6
7
8
9
def b(str)
    str.reverse.each_char.with_index.inject(0) {|r,(s,i)|
        r |= s.to_i << i
    }
end

p b"01101001"
p  "01101001".to_i(2)
p  0b1101001
0b か 0B で始めると２進整数リテラル。 
1
2
3
4
5
0b1010.p;
// => 10

0B0110_1001.p;
// => 105 (アンダーバーは無視される)

コンパイル時の定数の畳み込みにこだわって、C++のtemplateを使ってみました。
2進数8桁までの対応です。

デフォルト引数の値を0にすると、引数省略したときに位が上がってしまうため、
2という定数を引数が省略されたマークとして使い、桁ずらしを行っています。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
template <int a = 2, int b = 2, int c = 2, int d = 2, int e = 2, int f = 2, int g = 2, int h = 2>
struct Bin {
     enum {
        v = (h != 2) ? ((((((a * 2 + b) * 2 + c) * 2 + d) * 2 + e) * 2 + f) * 2 + g) * 2 + h
          : (g != 2) ?  (((((a * 2 + b) * 2 + c) * 2 + d) * 2 + e) * 2 + f) * 2 + g
          : (f != 2) ?   ((((a * 2 + b) * 2 + c) * 2 + d) * 2 + e) * 2 + f
          : (e != 2) ?    (((a * 2 + b) * 2 + c) * 2 + d) * 2 + e
          : (d != 2) ?     ((a * 2 + b) * 2 + c) * 2 + d
          : (c != 2) ?      (a * 2 + b) * 2 + c
          : (b != 2) ?       a * 2 + b
          : (a != 2) ?       a
          : 0
    }; 
};

void test()
{
    int n000 = Bin<                      >::v;
    int n001 = Bin<                     1>::v;
    int n002 = Bin<                  1, 0>::v;
    int n005 = Bin<               1, 0, 1>::v;
    int n010 = Bin<            1, 0, 1, 0>::v;
    int n021 = Bin<         1, 0, 1, 0, 1>::v;
    int n042 = Bin<      1, 0, 1, 0, 1, 0>::v;
    int n085 = Bin<   1, 0, 1, 0, 1, 0, 1>::v;
    int n170 = Bin<1, 0, 1, 0, 1, 0, 1, 0>::v;
}

/*
   コンパイル結果の一部
  定数はコンパイル時に計算されてました。
*/

?test@@YAXXZ PROC NEAR                    ; test
; File c:\src\cons\dk98.cpp
; Line 17
    push    ebp
    mov    ebp, esp
    sub    esp, 36                    ; 00000024H
; Line 18
    mov    DWORD PTR _n000$[ebp], 0
; Line 19
    mov    DWORD PTR _n001$[ebp], 1
; Line 20
    mov    DWORD PTR _n002$[ebp], 2
; Line 21
    mov    DWORD PTR _n005$[ebp], 5
; Line 22
    mov    DWORD PTR _n010$[ebp], 10        ; 0000000aH
; Line 23
    mov    DWORD PTR _n021$[ebp], 21        ; 00000015H
; Line 24
    mov    DWORD PTR _n042$[ebp], 42        ; 0000002aH
; Line 25
    mov    DWORD PTR _n085$[ebp], 85        ; 00000055H
; Line 26
    mov    DWORD PTR _n170$[ebp], 170        ; 000000aaH
; Line 27
    mov    esp, ebp
    pop    ebp
    ret    0
?test@@YAXXZ ENDP                    ; test

2進数のリテラル表記はないので

1
Integer.parseInt("01101001", 2);

基準の最後に「定数に変換される」がありますので、一応、定数として宣言したほうが題意にあっているのではないかと考えました。

1
2
3
4
5
6
7
public class Sample {
    public static final int B01101001 = Integer.parseInt("01101001", 2);

    public static void main(String[] args) {
        System.out.println(B01101001);
    }
}

カンマがいらない形で....。これ使うくらいなら素直にビットフィールドの構造体定義するか、std::bitset使うけど；；

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
inline unsigned long bin(unsigned long n)
{
    return ((((n % 100000000) / 10000000) * 0x80) |
            (((n %  10000000) /  1000000) * 0x40) |
            (((n %   1000000) /   100000) * 0x20) |
            (((n %    100000) /    10000) * 0x10) |
            (((n %     10000) /     1000) * 0x08) |
            (((n %      1000) /      100) * 0x04) |
            (((n %       100) /       10) * 0x02) |
            (((n %        10) /        1) * 0x01));
}

void func()
{
    unsigned long n = bin(1000000);
}

さっき同じこと実験しててハマりました。

最上位が0の場合8進数として認識されます。

ってことでマクロで修正。

あと最適化されないけど、文字列版も

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/*bin_n(00111100)と書きます。
*/
#define  bin_n(n) \
    ((((0##n%0100000000)/010000000)<<7)\
    +(((0##n%0010000000)/001000000)<<6)\
    +(((0##n%0001000000)/000100000)<<5)\
    +(((0##n%0000100000)/000010000)<<4)\
    +(((0##n%0000010000)/000001000)<<3)\
    +(((0##n%0000001000)/000000100)<<2)\
    +(((0##n%0000000100)/000000010)<<1)\
    +(((0##n%0000000010)/000000001)   ))

/*文字列使用版
こちらも同じくbin_s(00111100)と書きます。
*/
#define bin_s(str)\
    (((#str[0]-'0')<<7)+((#str[1]-'0')<<6)+((#str[2]-'0')<<5)\
    +((#str[3]-'0')<<4)+((#str[4]-'0')<<3)+((#str[5]-'0')<<2)\
    +((#str[6]-'0')<<1)+#str[7]-'0')
}

なるほど。 先頭0付けると8進数って、0x付けると16進数ってぇのと大差ない感覚だったんですけど。

マクロは、拡張も楽な感じ。（コードは試してません）

1
2
3
4
#define bin_8(a)                bin_n(a)
#define bin_16(a,b)             ((bin_8(a)<<8)|bin_8(b))
#define bin_32(a,b,c,d)         ((bin_16(a,b)<<16)|bin_16(c,d))
#define bin_64(a,b,c,d,e,f,g,h) ((bin_32(a,b,c,d)<<32)|bin_32(e,f,g,h))

Gaucheならそのまま書けますね。

1
2
gosh> #b01101001
105

GaucheならというかSchemeなら、でした。

なんとなく36進数まで対応してみました。
もっと良い方法がありそうですが。

10:user> #,(r 2 "01101001")
=> 105
11:user> #,(r 16 "ff")
=> 255
12:user> #,(r 36 "10")
=> 36

1
2
3
(define-reader-ctor 'r
  (lambda (radix string)
    (string->number string radix)))
Erlang なら 2 進数から 36 進数リテラルまで完備 :-) 
1
2
3
4
5
Eshell V5.5.5  (abort with ^G)
1> 2#01101001.
105
2> 36#01101001.
2237295169

Bashの場合はbase#nという形式で表現します。

1
2
$ echo $[2#11111111]
255

すみません。言語を入れ忘れてしまったようです。 Bashに直してください。

C++ でやるのはちょっと前に話題になってましたね。 でそれを参考にテンプレート特殊化とプリプロセッサマクロを使ったやつを。

8進数リテラルを使うので桁数に限界があります。unsigned long long が 64bits の環境で22桁ほど。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

template<unsigned long long n, int base = 8>
struct binary {
    enum {
        value = (binary<n / base>::value << 1) + (n % base == 1 ? 1 : 0)
    };
};

template<>
struct binary<0> {
    enum {
        value = 0
    };
};

#define BIN(n) binary<0 ## n ## ul>::value

int main()
{
    std::cout << BIN(1101001) << std::endl; // => 105
    std::cout << BIN(1111111111111111111111) << std::endl; // => 4194303
    return 0;
}

1
2
3
bin = lambda *a: sum([1 << i for i, j in enumerate(reversed(a)) if j])

bin(0,1,1,0,1,0,0,1)

ビルトイン関数 bin2dec() があります．

see: MATLAB Function Reference: bin2dec 

1
bin2dec('01101001')

ビルトイン関数 bin2dec() があります．

see: MATLAB Function Reference: bin2dec 

1
bin2dec('01101001')
来てみたらもう次のお題が出てしまっていたので、用意していた私の案を公開します。

Cのマクロによる実装です。
引数に二進数表現を受け取り、#によってダブルクォーテーションでくくって文字列にします。
ここで、文字列リテラルのサイズ(NULL文字含む)がsizeof("str")で取得できる(この場合4)を利用して、左の方が足りないときは0と見なします。そうでないなら文字コードの'0'と'1'で判定します。
#4585を任意文字数にした感じでしょうか。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/* 使用例 0を詰めても桁数が半端でも大丈夫 bintest.c */
#include <stdio.h>
#include "binary.h"

int main(){
    printf("%u\n", bin(0111));
    printf("%u\n", bin(11111));
    printf("%u\n", bin(11111111111111111111111111111111));
}


/* ２進数記述マクロ binary.h */
#ifndef BINARY_H_INCLUDE
#define BINARY_H_INCLUDE

#define bin(n) ((sizeof(#n)<33?0:(#n[sizeof(#n)-33]-'0') << 31) |\
(sizeof(#n)<32?0:(#n[sizeof(#n)-32]-'0') << 30) |\
(sizeof(#n)<31?0:(#n[sizeof(#n)-31]-'0') << 29) |\
(sizeof(#n)<30?0:(#n[sizeof(#n)-30]-'0') << 28) |\
(sizeof(#n)<29?0:(#n[sizeof(#n)-29]-'0') << 27) |\
(sizeof(#n)<28?0:(#n[sizeof(#n)-28]-'0') << 26) |\
(sizeof(#n)<27?0:(#n[sizeof(#n)-27]-'0') << 25) |\
(sizeof(#n)<26?0:(#n[sizeof(#n)-26]-'0') << 24) |\
(sizeof(#n)<25?0:(#n[sizeof(#n)-25]-'0') << 23) |\
(sizeof(#n)<24?0:(#n[sizeof(#n)-24]-'0') << 22) |\
(sizeof(#n)<23?0:(#n[sizeof(#n)-23]-'0') << 21) |\
(sizeof(#n)<22?0:(#n[sizeof(#n)-22]-'0') << 20) |\
(sizeof(#n)<21?0:(#n[sizeof(#n)-21]-'0') << 19) |\
(sizeof(#n)<20?0:(#n[sizeof(#n)-20]-'0') << 18) |\
(sizeof(#n)<19?0:(#n[sizeof(#n)-19]-'0') << 17) |\
(sizeof(#n)<18?0:(#n[sizeof(#n)-18]-'0') << 16) |\
(sizeof(#n)<17?0:(#n[sizeof(#n)-17]-'0') << 15) |\
(sizeof(#n)<16?0:(#n[sizeof(#n)-16]-'0') << 14) |\
(sizeof(#n)<15?0:(#n[sizeof(#n)-15]-'0') << 13) |\
(sizeof(#n)<14?0:(#n[sizeof(#n)-14]-'0') << 12) |\
(sizeof(#n)<13?0:(#n[sizeof(#n)-13]-'0') << 11) |\
(sizeof(#n)<12?0:(#n[sizeof(#n)-12]-'0') << 10) |\
(sizeof(#n)<11?0:(#n[sizeof(#n)-11]-'0') << 9) |\
(sizeof(#n)<10?0:(#n[sizeof(#n)-10]-'0') << 8) |\
(sizeof(#n)<9?0:(#n[sizeof(#n)-9]-'0') << 7) |\
(sizeof(#n)<8?0:(#n[sizeof(#n)-8]-'0') << 6) |\
(sizeof(#n)<7?0:(#n[sizeof(#n)-7]-'0') << 5) |\
(sizeof(#n)<6?0:(#n[sizeof(#n)-6]-'0') << 4) |\
(sizeof(#n)<5?0:(#n[sizeof(#n)-5]-'0') << 3) |\
(sizeof(#n)<4?0:(#n[sizeof(#n)-4]-'0') << 2) |\
(sizeof(#n)<3?0:(#n[sizeof(#n)-3]-'0') << 1) |\
(sizeof(#n)<2?0:(#n[sizeof(#n)-2]-'0') << 0))

#endif


/* binary.h生成プログラム binary.c */
#include <stdio.h>

#define BIT 32

int main(){
    int i;
    freopen("binary.h", "w", stdout);
    puts("#ifndef BINARY_H_INCLUDE");
    puts("#define BINARY_H_INCLUDE");
    puts("");

    printf("#define bin(n) (");
    for(i=0; i<BIT; i++){
        printf("(sizeof(#n)<%d?0:(#n[sizeof(#n)-%d]-'0') << %d)", BIT-i+1, BIT-i+1, BIT-i-1);
        if(i != BIT-1)
            printf(" |\\\n");
    }
    printf(")\n");

    puts("");
    puts("#endif");
}

リテラル表記は出来ませんがbindec関数が用意されてます。

1
2
3
4
$i = bindec("01101001"); // 105

// 0,1のみをgrepした計算結果になる
$i = bindec("01101201"); // 53 = 0110101
PostScript も 2 進数から 36 進数まで書けますよ 
1
2
3
4
GS>2#100 =
4
GS>36#wxyz =
1537019