counting-bits

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an integer <code>n</code>, return an array <code>ans</code> of length <code>n + 1</code> such that for each <code>i</code> (<code>0 &lt;= i &lt;= n</code>), <code>ans[i]</code> is the number of <code>1</code>&#39;s in the binary representation of <code>i</code>.

&nbsp;
Example 1:

<pre>
Input: n = 2
Output: [0,1,1]
Explanation:
0 --&gt; 0
1 --&gt; 1
2 --&gt; 10
</pre>

Example 2:

<pre>
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --&gt; 0
1 --&gt; 1
2 --&gt; 10
3 --&gt; 11
4 --&gt; 100
5 --&gt; 101
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>0 &lt;= n &lt;= 105</code></li>
</ul>

&nbsp;
Follow up:

<ul>
	<li>It is very easy to come up with a solution with a runtime of <code>O(n log n)</code>. Can you do it in linear time <code>O(n)</code> and possibly in a single pass?</li>
	<li>Can you do it without using any built-in function (i.e., like <code>__builtin_popcount</code> in C++)?</li>
</ul>

countBits

Counting Bits

Number of 1 Bits

number-of-1-bits

位1的个数

Sum of Values at Indices With K Set Bits

sum-of-values-at-indices-with-k-set-bits

计算 K 置位下标对应元素的和

Find the K-or of an Array

find-the-k-or-of-an-array

找出数组中的 K-or 值

Bit Manipulation

Dynamic Programming

给你一个整数 <code>n</code> ，对于&nbsp;<code>0 &lt;= i &lt;= n</code> 中的每个 <code>i</code> ，计算其二进制表示中 <code>1</code> 的个数 ，返回一个长度为 <code>n + 1</code> 的数组 <code>ans</code> 作为答案。

&nbsp;

<div class="original__bRMd">
<div>
示例 1：

<pre>
输入：n = 2
输出：[0,1,1]
解释：
0 --&gt; 0
1 --&gt; 1
2 --&gt; 10
</pre>

示例 2：

<pre>
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --&gt; 0
1 --&gt; 1
2 --&gt; 10
3 --&gt; 11
4 --&gt; 100
5 --&gt; 101
</pre>

&nbsp;

提示：

<ul>
	<li><code>0 &lt;= n &lt;= 105</code></li>
</ul>

&nbsp;

进阶：

<ul>
	<li>很容易就能实现时间复杂度为 <code>O(n log n)</code> 的解决方案，你可以在线性时间复杂度 <code>O(n)</code> 内用一趟扫描解决此问题吗？</li>
	<li>你能不使用任何内置函数解决此问题吗？（如，C++ 中的&nbsp;<code>__builtin_popcount</code> ）</li>
</ul>
</div>
</div>