(注：2017/04/27、いただいたフィードバックを元に翻訳を修正いたしました。) この記事では、皆さん（特にC言語のプログラマ）に「自分はCを分かっていなかった」と気付いてもらうことを目標にしています。 Cの落とし穴は、思っているよりもずっと身近なところにあります。ちょっとしたコードにも 未定義の動作 が潜んでいることを以下で示しましょう。 この記事はQ&A形式になっており、それぞれの例題は独立したソースコードとして扱ってください。 1. Q: これは正しいコードでしょうか？　（変数の二重定義エラーが発生するでしょうか。上述の通り、これは独立したソースファイルであり、関数本体や複合ステートメントの一部ではありません） 解答 A: 正しいコードです。1行目は仮定義であり、2行目でコンパイラが処理した後に “定義” になります。 2. extern void bar(void); void

「Cならわかるよ」というプログラマーは大勢います。確かにCの文法はよく知られているし、44年の歴史を誇るわけだし、あいまいな機能に悩まされることもありません。簡単ですよね！ あ、「Cならわかるよ」と 言うだけなら 簡単ですよねっていう意味ですよ。学校で習った人もいるだろうしお仕事で使ったことがある人もいるでしょう。覚えることもそんなに多くないし、完璧だという人もいるかもしれません。いいでしょう。でも、Cって実は、そんなにシンプルではないのです。 嘘だと思うなら、今から挙げる問題を解いてみましょう。たった5問です。基本的にはどれも同じで「戻り値は何ですか？」という問題ばかりです。四択方式で、どの問題も正解はひとつだけです。さあどうぞ。 第1問

(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) C言語の規格のリビジョン間には微妙な違いがありますが、このことを利用して「C90、C99、C11のどれとしてコンパイルされたかどうかにより、違う挙動をする」というプログラムを作ることが可能です。同様に、C++はほぼC言語の上位互換ですが、C言語とC++で違った結果を生み出すプログラムも存在します。 これは2015年の International Obfuscated C Code Contest (難読Cコード・国際コンテスト)への Don Yangの投稿 において、 C89、C99、C11、C++98、C11のどれとしてコンパイルされるかによって異なる出力を生成するプログラムを作成するのに使われています。C90の場合は、以下のような星形を出力します。 **************************

Sublime Text は、私のお気に入りのプログラミング用テキストエディタです。 Sublime Textで気に入っている特徴の1つは、あいまい検索アルゴリズムです。ファイルや関数の検索が超高速なのです。これまで多くの人が、インターネット上で、この仕組みについて質問していましたが、満足の行く回答はありませんでした。そこで、私が自らこれを解明することにしました。 全部読むのが面倒な方へ 本文を読まずに最終結果だけ知りたいですか？　了解！　私は、あなたを責めたりしませんよ。 インタラクティブなデモ： こちらをクリック ソースコード： C++ 、 JavaScript Sublime Textの仕組み Sublime Textのあいまい一致とは何でしょうか。そして、なぜそれはそんなに賢いのでしょうか。聞いてくれてうれしいです。 Sublime Textには、2つの非常に便利なナビゲーション関

先日、アルゴリズムの授業でソートのアルゴリズムをいくつか習いました。ソートアルゴリズムの名前と原理くらいは聞いたことがありましたが、実装したことはなかったのでいい機会だと思い実装してみることにしてみました。ただ実装するだけでは面白くないので高速化の限界に挑戦してみたいと思います。 計測用プログラム 今回の計測では、ランダム値が入った配列のソートを100回行い、平均時間を各アルゴリズムに競わせるというシンプルなルールにしました。プログラムは以下の通りです。 C++11で入ったメルセンヌ・ツイスタなどの機能を使っているので、ビルド時には-std=c++11を指定する必要があります。 実験に使用したパソコンのCPUはCore i3-3227U@1.90GHz、コンパイラはgcc version 4.8.4で最適化オプションには-O3を指定しました。 #include <iostream> #in

C言語を久しぶりに触ってやっと理解できたのが、配列は第一級オブジェクト（ファーストクラスオブジェクト） ではない 、ということです。 第一級オブジェクト - Wikipedia 第一級オブジェクト Wikipediaによると、第一級オブジェクトと呼ばれるものは以下の様な特徴を持つそうな。 無名のリテラルとして表現可能である。 変数に格納可能である。 データ構造に格納可能である。 それ自体が独自に存在できる（名前とは独立している）。 他のものとの等値性の比較が可能である。 プロシージャや関数のパラメータとして渡すことができる。 プロシージャや関数の戻り値として返すことができる。 ... C言語だと、int(1, 2)やchar('a', 'b')、floatやboolなどがこれに相当します。また、任意の型へのポインタも、同じ性質を持っています。 私はC言語を真面目に勉強する前にJavaScr

C言語は宣言文が非常に読みにくいことで有名で、後発のGo言語はこれを批判して宣言の構文を変えています。私もずっと読むのが苦手だったのですが、私の頭が悪いのではなく、C言語の仕様がヘン、ということらしい。 今まで飽きるほどこの手の解説は書かれてきてるわけですが、自分なりにまとめないと覚えた気がしないので、あえてまとめておきます。ここに書いてある内容は、「C言語ポインタ完全制覇」に詳しく書いてあります。 型の派生 C言語では、int, char, floatなどの基本型から、配列やポインタを派生していくことができます。対象を並べたものが配列で、対象を指し示すのがポインタです。 配列やポインタからも配列やポインタを派生できるので、派生パターンは無限に存在します。 int int　の配列 int　の配列　の配列 ... int　へのポインタ int　へのポインタ　へのポインタ ... int　への

今回の目的 例えば 他のデバイスが非同期でフラグを変えるのを待つ場合に コンパイラの最適化によって、望んだ処理が消える可能性がある その場合に volatileを使うが、そのあたりを調査します 問題コード まず簡単な例。flagが初期値0で、0以外の値に変わると worker!! と出力し、終了する。 別スレッドで 5秒後にflag=1 に設定するので５秒後に終了するはずのプログラム （下記に理由を書きますが　本来はスレッドの同期にvolatileを使うのは間違いで、処理系によっては正しく動作できません。今回はそのあたりは無視しています） #include <iostream> #include <thread> int flag = 0; void worker() { while( flag == 0){ } std::cout << "worker!! \n"; } auto mai

はじめに この記事では、プログラムの計算量を求める方法を説明します。プログラミングの初心者向けに、厳密さよりも分かりやすさを優先して説明していきます。 サンプルコードについて この記事のサンプルコードは、C言語（C99）で記述しています。 計算量とは？ 計算量とは、 「そのプログラムがどれくらい速いかを大雑把に表す指標」 です。 もう少し正確に言うと、 「入力サイズの増加に対して、実行時間がどれくらいの割合で増加するかを表す指標」 です。 グラフによる計算量の表現 計算量をグラフで表すと、以下のようになります。 これは、「入力サイズ $n$ が増加するにつれて、実行時間が $n$ に比例して増加する」ということを表しています。 別のグラフも見てみましょう。 これは、「入力サイズ $n$ が増加するにつれて、実行時間が $n^2$ に比例して増加する」ということを表しています。 計算量を求め

半年に一度くらい、古いコードで使っている再帰呼び出しが原因でスタックオーバーフローになるという不具合が発見され、その都度ループで書き直す修正を入れている。再帰呼び出しをループに展開する方法は、「幅優先探索」や「深さ優先探索」というキーワードで探すと見つけることができる。そのエッセンスだけメモしておく。 再帰呼び出しのうち、トップダウンで処理していくものについては、キューを使うと比較的簡単に展開できる。たとえば struct Node { Node* left; Node* right; : };という構造体があって、 void ProcessNode(Node* node) { : : (do something) : if (node->left) ProcessNode(node->left); if (node->right) ProcessNode(node->right); }の

よく定数を忘れるので備忘 float の誤差を考慮して等価比較するには FLT_EPSILON を使う double のための DBL_EPSILON long double のための LDBL_EPSILON も用意されている。 例えば float a が float b とイコールであるかをチェックするには a と b との差が FLT_EPSILON の値以下かどうか、つまり差の絶対値を FLT_EPSILON と比較演算する。 これが float a; float b; // 何らかの処理 if (a == b) { } こうなる ↓ float a; float b; // 何らかの処理 if (fabsf(a - b) < FLT_EPSILON) { } double の場合は ↓ double a; double b; // 何らかの処理 if (fabs(a - b) <

2016/07/18追記 CountingSortについて誤りがあったため訂正しました ソートアルゴリズム全般考察 典型的なソートアルゴリズムでは、最善で $O(n log n)$ 、最悪で $O(n^2)$ である。理想は $O(n)$ である。 比較ソートでは、必ず $O(n log n)$ の比較が必要となる。 汎用手法による分類。挿入、交換、選択、マージなどがある。 Wikipedia https://ja.wikipedia.org/wiki/ソート 授業で習った基本的なソートアルゴリズムをまとめたいと思います。 実際はライブラリを使うかもしれませんが、内部を知っていて損はないので覚書です。 まとめるソートアルゴリズム バブルソート 選択ソート Counting Sort マージソート クイックソート 奇偶転置ソート バブルソート バブルソート (bubble sort) は、ソ

んじゃ、解説するよ。何のことかわからない人は前の記事を読んでね。 C言語の仕様を把握せよ！ 手元に教科書は置いているかな。なに、高いって？まぁ、俺も持ってないけど。仕方がないので、教科書の草書を見てくれ。 さて、なぜ前の記事のようになったかであるが、C言語の仕様に基づいて動作した結果であるとしか言いようがない。ただし、動作には環境依存の部分もある。前の記事はMac OS X(64bit)上のClangでの結果だ。この環境はLP64(int:32/long:64/void*:64)なので、それにあわせて説明する。ILP32(32bitの環境)やLLP64(64bitのVC++)とは少しだけ動作が異なるので、注意して欲しい(ただ、現象としては普通のPCなら同じになるはず)。では、今回の動作に関係がある仕様を見ていこう。 -はリテラルではなく単項演算子 一つ目の注意点は-である。-1と書いたとき

はじめに C / C++ では Java などの他の言語では使えない「共用体」と「ビットフィールド」という機能があります。これらは、システム記述言語として C らしい機能です。 共用体とは まず、共用体ですが構造体に似ていますが、構造体と異なり１つのメモリ領域を使います。したがって、あるフィールドが変更されると、他のフィールドが影響を受ける場合があります。 共用体の使い道ですが、あるワードの上位バイトと下位バイトを入れ替えるとか、いくつかのバイトからなるデータを１回でクリアしたいとかなどが考えられます。 共用体のサンプル #include void main() { union LongWord { long int lw; int iw[2]; short sw[4]; unsigned char b[8]; }; union LongWord ld; ld.lw = 0; ld.sw[

コンソール制御の話をしていこうと思う。 ここでは必要となる基本的な制御コードと、 その記述に必要なエスケープシーケンスについて説明する。 制御コード まず制御コードについて簡単に説明する。 現在一般的に使用されている、半角英数字を表現するのに使われている1byteコードは、 ASCII（American Standard Code for Information Interchange）コードである。 ASCIIコードは1byte=8bitのうち、7bitを利用し、各番号に文字が割り当てていて、その羅列で文字列を表現する。 しかし、英語圏で使われる、英数字、記号は合わせて割り当てても、7bit=128パターンにあまりがある。 その余った領域に表示文字以外の意味が割り当てられている。これを制御コードと呼んでいる。 制御コードと言われると、何やら難しい物を想像するかもしれないが、何も特別なもの

前回は、 一般的な文字列リテラルに、制御コード等を記述するためのエスケープシーケンスについて解説した。 これの発展形、というか、より柔軟な指定ができ自由度の高い制御方法として、ANSIエスケープコードというものがある。 以前の記事で、簡単な一覧を紹介したことがあるが、 改めて整理して紹介してみようと思う。 そもそもエスケープシーケンスは、狭義にはエスケープコードから始まるシーケンスなので、 むしろこちらのほうが本来のエスケープシーケンスというべきかもしれない。 ANSIエスケープコードとは 詳細な一覧は Wikipedia に英語ではあるが載っている。 できることは大まかにいうと、 コンソール上のカーソル位置の移動、出力済みテキストの消去、コンソールのスクロール、 テキストフォントの種別指定、前景色、背景色の指定、といったところになる。 いわゆる端末エミュレータと呼ばれるコンソールでこのシ

実用性がまるでありませんが、ビット演算子のみを利用した除算の例です。 +, -, 比較演算子, ループは使用していません。 http://ideone.com/FMuNWh #include <stdio.h> char add(char a, char b) { char r = 0; char n = 0; r |= (a & 0x1) ^ (b & 0x1); n = (a & 0x1) & (b & 0x1); r |= (((a >> 1) & 0x1) ^ ((b >> 1) & 0x1) ^ n) << 1; n = (((a >> 1) & 0x1) & ((b >> 1) & 0x1)) | (((a >> 1) & 0x1) & n) | (n & ((b >> 1) & 0x1)); r |= (((a >> 2) & 0x1) ^ ((b >> 2) & 0x1)

Spring BootによるAPIバックエンド構築実践ガイド 第2版 何千人もの開発者が、InfoQのミニブック「Practical Guide to Building an API Back End with Spring Boot」から、Spring Bootを使ったREST API構築の基礎を学んだ。この本では、出版時に新しくリリースされたバージョンである Spring Boot 2 を使用している。しかし、Spring Boot3が最近リリースされ、重要な変...

問．Cでオブジェクト指向プログラミングを行なえ。ただし「オブジェクト指向プログラミング」とは、次のような特徴を持つプログラミング技法であるものとする： オブジェクトの実装はオブジェクトのユーザーからは隠蔽される（カプセル化／隠蔽） 同一型のオブジェクトと同一メソッドを与えた時、実際のメソッドの動作はオブジェクトの内容により変化する（ポリモーフィズム／多態性） なお、ユーザーが既存のオブジェクトをカスタマイズして新たなオブジェクトを作成する機能は、必要ないものとする。 この問いの狙い よく、「オブジェクト指向プログラミング」と「オブジェクト指向言語」は混同されます。が、前者はプログラムを設計する上での考え方で、後者はその考え方を容易にソースコードに書けるような仕様になっている言語の事で、全く違うものを指しています。 その証拠を示すため、「非オブジェクト指向言語」たるC言語で「オブジェクト指向