1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

CodeIQ:「バイナリ・カウント」 問題

1
Last updated at Posted at 2026-04-04

Kawazoe(@riverplus)さんのCodeIQの問題です。
問題のページへのリンクが切れていますが、次のような問題です。
問題
与えられた数までの整数を二進数としたときその1の数の総数を答えてください
【解答】
・第1問:F(10^3) = 4938
・第2問:F(10^10) = 164293127179 

こちらにも情報があります。
->https://posfie.com/@riverplus/p/40uN35X?page=2
->https://posfie.com/@riverplus/p/40uN35X  (2026.11.12)
(web検索で偶々当たったのを書いてしまいました。今見に行って気が付きました)

解法
 0 0 0 0   2進数を縦に並べるとk桁目の0と1が
 0 0 0 1   2^(k-1)個ずつ続くことに気が付きます。
 0 0 1 0   k-1桁までが0から2^(k-1)-1を繰り返しますので当然です。
 0 0 1 1   これを利用して解きます。
 0 1 0 0
 0 1 0 1   k桁目の0,1の並びをそれぞれ一組にして
 0 1 1 0   合わせて何組あるか計算すると
 0 1 1 1   (d,m)= (x+1)) divmod 2^(k-1)としてd組となります。
 1 0 0 0   そのうち1の組の数は(d div 2)個で
       それぞれに1が2^(k-1)個含まれますので、
       1の数は(d div 2)*2^(k-1)です。
       端数の1の数はdが偶数なら次の数字が0なので0個、
       奇数なら次から1が続くのでm個です

#julia ver 1.41,1.53,1.85,1.12.1

function solve(n,a)
    sum ,x = 0 , 1
    while(x <= n)
      (d,m) = divrem(n+1,x) #0の部分を足す
      sum += div(d,2) * x 
      if isodd(d) sum += m end
      x *= 2
    end
    s = sum ==  a ? "ok " : "no "
   println(s,sum) 
end

solve(10^3,4938)
solve(10^10,164293127179)

最近古い言語のio、iconの後継のunicon、prologの発展系のpicatで遊んでいます。
そこで今回は簡単なコードでもあるし、Picatで書いてみました。
PicatについてAIさんにまとめてもらいました。

Picat:Prologの「探索力」と手続き型の「書きやすさ」を統合した言語

B-Prologの開発者によって設計されたPicatは、Prologをベースに、決定的な
実行(コミット)と強力なループ構文、そして強力なソルバーを内蔵した言語です。

■ 4つのルール記法:実行戦略の使い分け

記法 種類 特徴
Head = Result 関数型 戻り値を返す決定的な定義。代入式で呼び出し可能。
Head => Body コミット型 条件一致でルール固定。バックトラックせず高速。
Head ?=> Body 非コミット型 実行後、失敗時は「次のルール」も試すガード付き探索用。
Head :- Body Prolog型 伝統的なホーン節。全解を網羅するレガシー互換。

■ Picatを最強にする3つの武器

  1. 強力な制御構造
    foreach等のループ、ifやcond、リスト内包表記、破壊的代入(:=)を備え、
    手続き型の感覚で記述可能。
     
  2. 制約論理プログラミング (CLP)
    cp, sat, mip モジュールを内蔵。数独から複雑なスケジュール最適化まで、
    制約を記述するだけで超高速に解く。
     
  3. テーブル化 (Tabling)
    述語に table と宣言するだけで計算結果を自動キャッシュ。
    再帰的な動的計画法(DP)を、メモ化のコードなしで一瞬で実装可能。

Picatでの解法
最初の0の列を消して1と0の並び一つずつを合わせて一組とする方法もあります。
k桁目は下位から2^(k-1)個がなく、また一組の数が2^kとなりますので、
(d,m)=(x-2^(k-1)+1) divmod 2^kとすると、割り切れる部分の1の数はd*2^(k-1)個。
端数の1の数はm>2^(k-1) なら2^(k-1)個,m=<2^(k-1)ならm個 です。
今回はprologい寄せて述語形式で書きました。

なおPicatはweb上のplayground類が見つからず、AIに聞きながら
 WSL + Picat + VsCode + VSC-Picat + Code Runner
の環境を作って走らせています。設定は最低限ですが下記で何とか動いています。

  "picat.executablePath": "/home/***/Picat/picat"
  "code-runner.executorMap":
    "picat": "cd \$dir && ~/Picat/picat $fileName"
  "code-runner.runInTerminal": true
 (Picatの部分のみ抽出)

Code-Runnuerのrunボタン あるいは右クリックして 「Picat:run doccument」で
consultとmainの実行がなされます。
またはteaminalで「picat」を入力してpicatに入り「cl('path/filename').」
でmain以外の関数や述語も実行できます。

% Picat v 3.9#7
%VsCode + WSL + VSC-Picat + Code Runner

main =>       %mainを自動で選択
  Data = [[10**3,4938],[10**10,164293127179]],
  foreach([N,A] in Data)
    if solve(N,R) then
      Str = cond(R == A, " ok  ", " no  "),
      printf(" %s %w->%w%n", Str, N, R)
    else
      printf(" fail %w%n", N)
    end
  end.
     
solve(N,R) =>
  Sum = 0,                             %  = 変数に値を確定させる
  X = 1,
  while(X<=N)
    D := (N-X+1) div (X*2),            % := 値を変更(更新)する
    M := (N-X+1) mod (X*2),
    Sum := Sum + D*X + min(M,X),
    X := X*2,
  end,
  R = Sum.  
---
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?