C++のbitsetに関するメモ

競技プログラミングで使いたいと思いつつずっと未履修だったbitsetの使い方を勉強しました。

基本操作

以下ではすべて以下が書かれているものとします。

#include <bitset>
#include <iostream>
using namespace std;

初期化は、文字列を与えるか、整数を与えるかで行えます。

int main(void)
{
    bitset<8> bs1("10001111");
    cout << bs1 << endl;  // 10001111

    bitset<8> bs2(127);
    cout << bs2 << endl;  // 01111111

    return 0;
}

n桁目を1にするにはset, n桁目を0にするにはresetを使うのがシンプルです。

int main(void)
{
    bitset<8> bs("10001111");
    cout << bs << endl;  // 10001111

    bs.set(4); // 4番目の桁を1に変更
    cout << bs << endl;  // 10011111

    bs.reset(2); // 2番目の桁を0に変更
    cout << bs << endl;  // 10011011

    return 0;
}

n番目の桁を1にするか0にするかを変数で制御したい場合は、引数が2個バージョンのset()を使います。

int main(void)
{
    bitset<8> bs("10001111");
    cout << bs << endl;  // 10001111

    bs.set(4, 1); // 4番目の桁を1に変更
    cout << bs << endl;  // 10011111

    bs.set(2, 0); // 2番目の桁を0に変更
    cout << bs << endl;  // 10011011

    return 0;
}

引数なしでset(), reset()を呼ぶと、ビットが1または0で埋められます。

int main(void)
{
    bitset<8> bs("10001111");
    cout << bs << endl;;  // 10001111

    bs.set();
    cout << bs << endl;  // 11111111

    bs.reset();
    cout << bs << endl;  // 00000000

    return 0;
}

n番目の桁が0か1かを確かめるには、添字かtest()を使います。

int main(void)
{
    bitset<8> bs("10001111");
    cout << bs << endl;

    // 1,1,1,1,0,0,0,1, と表示される
    for(size_t i = 0; i < bs.size(); ++i) {
        cout << bs[i] << ",";
    }
    cout << endl;

    // 同上
    for(size_t i = 0; i < bs.size(); ++i) { 
        cout << bs.test(i) << ",";
    }

    return 0;
}

当然、ビット演算も可能です。

int main(void)
{
    bitset<8> bs1("10001111");
    bitset<8> bs2("01010101");

    cout << (bs1 & bs2) << endl;  // 00000101
    cout << (bs1 | bs2) << endl;  // 11011111
    cout << (bs1 ^ bs2) << endl;  // 11011010

    return 0;
}

count()で1が立ったビットの数を数えられるのはかなり便利です。

int main(void)
{
    bitset<8> bs(127);
    cout << bs.count() << endl;  // 7
    return 0;
}

その他、使う可能性が高そうな便利機能です。

int main(void)
{
    bitset<8> bs("10001111");
    cout << bs << endl;  // 10001111

    // 0と1を反転
    bs.flip();
    cout << bs << endl;  // 01110000

    // 左に2個シフト
    bs <<= 2;
    cout << bs << endl;  // 11000000

    // 右に2個シフト
    bs >>= 2;
    cout << bs << endl;  // 00110000

    // 整数に変換
    unsigned long n = bs.to_ulong();
    cout << n << endl;  // 48

    // 文字列に変換
    string str = bs.to_string();
    cout << str << endl;  // 00110000

    // 文字列に変換する際、0, 1それぞれを任意の記号にすることも可能
    string str2 = bs.to_string('a', 'z');
    cout << str2 << endl;  // aazzaaaa

    return 0;
}

応用例

ビット全探索

2の5乗をビット探索するときは以下のように書きます。

int main(void)
{
    for(int i = 0; i < (1 << 5); ++i) {
        bitset<5> s(i);
        cout << s << endl;
    }
    return 0;
}

出力は以下です。

00000
00001
00010
00011
...
11110
11111

参考URL

nkfの使い方のメモ

ファイルの文字コードと改行コードを調べる

nkf --guessを使います。

$ nkf --guess a.cpp
UTF-8 (CRLF)

UTF-8 (BOM付)の場合は以下のように表示されます。

$ nkf --guess a.cpp
UTF-8 (BOM) (CRLF)

文字コードや改行コードを変換する

例えば改行コードをCRLFに変換する場合は-Lwを使って以下のように書きます。

$ nkf -Lw before.cpp > after.cpp

直接ファイルを書き換える場合は、以下のように--overwriteをつけます。

$ nkf -Lw a.cpp --overwrite

以下、個人的によく使うオプションです。

引数 結果
-Lu 改行コードをUnix(LF)に変換
-Lw 改行コードをWindows(CRLF)に変換
-Lm 改行コードをMac(CR)に変換
-w 文字コードUTF-8コードに変換
-w8 文字コードUTF-8コード(BOM有)に変換
-s 文字コードをShift-JISコードに変換

lessとlvの使い方の比較

これまで私はずっとlvというテキストビューワーを癖で使い続けてきました。 lvはShift_JISeuc_jpのファイルも文字化けなしで閲覧できるメリットがありますが、 最近はそもそもutf-8以外のファイルを扱うことがほぼなくなってきて、このメリットが薄くなってきました。 また、おそらくv.4.51 (Jan.16th,2004) から更新がないツールを使い続けるのもやや不安です。 初めからインストールされているlessを使っていけるように、lessのことを調べた結果を以下にまとめます。

lessとlvで同じ

内容 コマンド
文字列の前方検索 /
文字列の後方検索 ?
30行目に移動 30g
ファイルの冒頭から20%地点に移動 20p|
ファイル先頭に移動 g または <
ファイル末尾に移動 G または >

lessとlvで異なる

内容 lvのコマンド lessのコマンド
ファイルの行番号を表示 できなさそう。nl (ファイルパス) | lvするしかない? 起動時にless -N、または閲覧中に-NしてEnter
ヘルプ表示 なし? h

lessでの文字列の検索Tips

例えば"a.txt"という文字列を検索したい場合、a.txtとそのまま検索すると、.正規表現扱いになりどんな文字ともマッチしてしまいます。代わりに a[.]txt とすれば.エスケープできます。これはlvでは無理な模様。

参考URL

Pythonのインデント系エラーと戦う

Pythonスクリプトを書いてflake8にかけると、インデント量や改行タイミングの微妙な違反によって

  • E125 continuation line with same indent as next logical line
  • E129 visually indented line with same indent as next logical line

といったエラーが出ます。エラー例と直し方の例をまとめていきます。

例1

def function_having_very_long_name(
    arg_having_very_very_very_very_very_very_very_long_name):
    pass

関数名・引数名の両方が長いときは、上記のように(の直後で改行を入れたくなります。 しかしこのコードにflake8をかけると

E125 continuation line with same indent as next logical line

と怒られます。

直し方は以下があります。

直し方1

def function_having_very_long_name(
        arg_having_very_very_very_very_very_very_very_long_name):
    pass

引数を4個後ろにずらす方法です。yapfやautopep8というフォーマッタはこう直しました。

直し方2

def function_having_very_long_name(
    arg_having_very_very_very_very_very_very_very_long_name,
):
    pass

これはblackというフォーマッタの直し方です。引数の最後に','が追加されていますがこれはblackの趣味だと思います。

例2

ifの条件部分がとても長い場合を考えます。

a = b = c = d = e = f = g = h = 100
if (a == 100 and b == 200 and c == 300 and d == 400 and
    e == 500 and f == 500 and g == 600 and h == 700):
    print("ok")

と改行して書きたくなりますが、これをflake8にかけると

E129 visually indented line with same indent as next logical line

とエラーが出てしまいます。e == 200print('ok')の文頭の位置が揃ってしまったのが原因です。

このエラーは遭遇する人が多いようで、 https://stackoverflow.com/q/181530E125 overreaches pep8 · Issue #126 · PyCQA/pycodestyle でいろんな直し方の議論があります。

今回はフォーマッタにお伺いを立てました。

直し方1

a = b = c = d = e = f = g = h = 100
if (a == 100 and b == 200 and c == 300 and d == 400 and
        e == 500 and f == 500 and g == 600 and h == 700):
    print("ok")

e == 500の部分を4つ後ろにずらす方法です。autopep8はこの方法をとりました。私も多分こうすると思います。

yapfの結果も似ていますが、改行の位置を勝手にいじりました。

a = b = c = d = e = f = g = h = 100
if (a == 100 and b == 200 and c == 300 and d == 400 and e == 500 and f == 500
        and g == 600 and h == 700):
    print("ok")

直し方2

blackは、以下のように条件部をすべて縦に並べるよう整形しました。一貫性はありますが、無駄に行数を使うのが嫌です。

a = b = c = d = e = f = g = h = 100
if (
    a == 100
    and b == 200
    and c == 300
    and d == 400
    and e == 500
    and f == 500
    and g == 600
    and h == 700
):
    print("ok")

NumPyで2つのベクトル配列に対して順に内積を計算

2つの同型のベクトル配列a, bがあったとします。shapeは、ベクトルの次元をD、ベクトルの数をNとして(N, D)だとします。

0番目からN-1番目まで順に内積を取っていき長さNの結果を得ることを考えます。専用の命令があるのかと思ったらどうやらないようで、 https://stackoverflow.com/questions/35090401/how-to-calculate-the-dot-product-of-two-arrays-of-vectors-in-python にある方法を使うのが正解のようです。

Pythonスクリプトのテンプレートを考えてみた

Pythonの書き捨てスクリプトを書く速度を上げられるように、Pythonスクリプトのテンプレートを考えてみました。

経験上、どんなスクリプトでも以下を心がけると良いことが多いです。

  • コードは全部メイン関数の中に入れて、グローバル変数は許容しない
  • 出力はなるべくprintではなくloggerを使い、常にファイル保存を心がける
  • ログは同内容を標準エラー出力とファイル出力に流す
  • 実行時引数や処理時間も常にログに残す
  • ファイルの先頭にスクリプトの概要を書く

テンプレートは以下です。 https://github.com/minus9d/python_exercise/blob/master/template/template.py にも同じものがあります。

"""
○○するスクリプト
"""
import argparse
import logging
from pathlib import Path
import sys
import time


def parse_args() -> argparse.Namespace:
    parser = argparse.ArgumentParser()

    parser.add_argument(
        '-o', '--outdir', default='./outdir',
        help="出力ディレクトリ")

    args = parser.parse_args()
    return args


def setup_logger(logger_path: Path) -> logging.Logger:
    """loggerオブジェクトを生成

    Args:
        logger_path (Path): ログの書き込み先

    Returns:
        logger: loggerオブジェクト
    """

    logger = logging.getLogger('my_logger')
    logger.setLevel(logging.DEBUG)

    stream_handler = logging.StreamHandler()
    file_handler = logging.FileHandler(logger_path)

    stream_handler.setLevel(logging.DEBUG)
    file_handler.setLevel(logging.DEBUG)

    handler_format = logging.Formatter('%(asctime)s : %(levelname)s : %(message)s')
    stream_handler.setFormatter(handler_format)
    file_handler.setFormatter(handler_format)

    logger.addHandler(stream_handler)
    logger.addHandler(file_handler)

    return logger


def write_arguments(logger: logging.Logger, args: argparse.Namespace):
    """実行時引数をloggerに記録
    """
    logger.info(f"sys.argv:")
    logger.info(f"    {sys.argv}")
    logger.info(f"parsed args:")
    for key, value in vars(args).items():
        logger.info(f"    {key}: {value}")


def main():
    start_time = time.perf_counter()

    args = parse_args()

    outdir = Path(args.outdir)
    outdir.mkdir(parents=True, exist_ok=True)

    logger_path = outdir / 'log.log'
    logger = setup_logger(logger_path)

    logger.info('start')
    write_arguments(logger, args)

    # ここに実処理を書く

    end_time = time.perf_counter()
    logger.info('finished ({:.2f} sec)'.format(end_time - start_time))


if __name__ == '__main__':
    main()

bashスクリプトでset -uしているときの unbound variable を回避する

bashスクリプトの定番テクニックで、set -uを冒頭に書いておくことで、未定義の変数をうっかり使った時点でスクリプトを終了させるようにする、というものがあります( 参考 )。しかし、PATHやPYTHONPATHにパスを追加するときに困ることがあります。例えば、以下のようにPYTHONPATHにパスを追加するスクリプト

#!/bin/bash
set -u

export PYTHONPATH=/path/to/somewhere:${PYTHONPATH}

を実行するとき、もしPYTHONPATHが未set状態なら、

bash_undefined.sh: line 4: PYTHONPATH: unbound variable

というエラーが出てしまいます。

回避方法はいくつかありそうです。

-vを使う方法

bash 4.2から、-vを使うことで変数がsetされているかどうかを確認できるようになったそうです ( shell - How to check if a variable is set in Bash - Stack Overflow )。これを使うと以下のようにかけます。

#!/bin/bash
set -u

PATH1=/path/to/somewhere
if [[ -v PYTHONPATH ]]; then
    export PYTHONPATH=${PATH1}:${PYTHONPATH}
else
    export PYTHONPATH=${PATH1}
fi

一時的にset -uをやめる方法

set +uset -uで挟んだ部分だけ未定義の変数が使えるようになります。

#!/bin/bash
set -u

set +u
export PYTHONPATH=/path/to/somewhere:${PYTHONPATH}
set -u

Shell Parameter Expansionを使う方法

Assigning default values to shell variables with a single command in bash - Stack Overflow によると、例えば${VARIABLE:-default}と書くとき、もし変数${VARIABLE}が未定義ならかわりにdefaultという文字列を使うという意味になります。これは Shell Parameter Expansion というテクニックだそうです。

いまの例だと、PYTHONPATHという変数が未定義な場合は空文字列で代替したいので、以下のように書けます。

#!/bin/bash
set -u

export PYTHONPATH=/path/to/somewhere:${PYTHONPATH:-}