给你一个整数 n ，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 109 + 7 取余的结果。

示例 1：

输入：n = 1
输出：1
解释：二进制的 "1" 对应着十进制的 1 。

示例 2：

输入：n = 3
输出：27
解释：二进制下，1，2 和 3 分别对应 "1" ，"10" 和 "11" 。
将它们依次连接，我们得到 "11011" ，对应着十进制的 27 。

示例 3：

输入：n = 12
输出：505379714
解释：连接结果为 "1101110010111011110001001101010111100" 。
对应的十进制数字为 118505380540 。
对 109 + 7 取余后，结果为 505379714 。

提示：

• 1 <= n <= 105

sort is a command-line utility that sorts lines of text from files or standard input and writes the result to standard output. By default, sort arranges lines alphabetically, but it supports numeric sorting, reverse order, sorting by specific fields, and more.

This guide explains how to use the sort command with practical examples.

sort Command Syntax #

The syntax for the sort command is as follows:

sort [OPTIONS] [FILE]...

If no file is specified, sort reads from standard input. When multiple files are given, their contents are merged and sorted together.

Sorting Lines Alphabetically #

By default, sort sorts lines in ascending alphabetical order. To sort a file, pass the file name as an argument:

sort file.txt

For example, given a file with the following content:

banana
apple
cherry
date

Running sort produces:

apple
banana
cherry
date

The original file is not modified. sort writes the sorted output to standard output. To save the result to a file, use output redirection:

sort file.txt > sorted.txt

Sorting in Reverse Order #

To sort in descending order, use the -r (--reverse) option:

sort -r file.txt

date
cherry
banana
apple

Sorting Numerically #

Alphabetical sorting does not work correctly for numbers. For example, 10 would sort before 2 because 1 comes before 2 alphabetically. Use the -n (--numeric-sort) option to sort numerically:

sort -n numbers.txt

Given the file:

10
2
30
5

The output is:

2
5
10
30

To sort numerically in reverse (largest first), combine -n and -r:

sort -nr numbers.txt

30
10
5
2

Sorting by a Specific Column #

By default, sort uses the entire line as the sort key. To sort by a specific field (column), use the -k (--key) option followed by the field number.

Fields are separated by whitespace by default. For example, to sort the following file by the second column (file size):

report.pdf 2500
notes.txt 80
archive.tar 15000
readme.md 200

sort -k2 -n files.txt

notes.txt 80
readme.md 200
report.pdf 2500
archive.tar 15000

To use a different field separator, specify it with the -t option. For example, to sort /etc/passwd by the third field (UID), using : as the separator:

sort -t: -k3 -n /etc/passwd

Removing Duplicate Lines #

To output only unique lines (removing adjacent duplicates after sorting), use the -u (--unique) option:

sort -u file.txt

Given a file with repeated entries:

apple
banana
apple
cherry
banana

apple
banana
cherry

This is equivalent to running sort file.txt | uniq.

Ignoring Case #

By default, sort is case-sensitive. Uppercase letters sort before lowercase. To sort case-insensitively, use the -f (--ignore-case) option:

sort -f file.txt

Checking if a File Is Already Sorted #

To verify that a file is already sorted, use the -c (--check) option. It exits silently if the file is sorted, or prints an error and exits with a non-zero status if it is not:

sort -c file.txt

sort: file.txt:2: disorder: banana

This is useful in scripts to validate input before processing.

Sorting Human-Readable Sizes #

When working with output from commands like du, sizes are expressed in human-readable form such as 1K, 2M, or 3G. Standard numeric sort does not handle these correctly. Use the -h (--human-numeric-sort) option:

du -sh /var/* | sort -h

4.0K /var/backups
16K /var/cache
1.2M /var/log
3.4G /var/lib

Combining sort with Other Commands #

sort is commonly used in pipelines with other commands.

To count and rank the most frequent words in a file, combine grep , sort, and uniq:

grep -Eo '[[:alnum:]_]+' file.txt | sort | uniq -c | sort -rn

To display the ten largest files in a directory, combine sort with head :

du -sh /var/* | sort -rh | head -10

To extract and sort a specific field from a CSV using cut :

cut -d',' -f2 data.csv | sort

Quick Reference #

Troubleshooting #

Numbers sort in wrong order
You are using alphabetical sort on numeric data. Add the -n option to sort numerically: sort -n file.txt.

Human-readable sizes sort incorrectly
Sizes like 1K, 2M, and 3G require -h (--human-numeric-sort). Standard -n only handles plain integers.

Uppercase entries appear before lowercase
sort is case-sensitive by default. Use -f to sort case-insensitively, or use LC_ALL=C sort to enforce byte-order sorting.

Output looks correct on screen but differs from file
Output redirection with > truncates the file before reading. Never redirect to the same file you are sorting: sort file.txt > file.txt will empty the file. Use a temporary file or the sponge utility from moreutils.

FAQ #

Does sort modify the original file?
No. sort writes to standard output and never modifies the input file. Use sort file.txt > sorted.txt or sort -o file.txt file.txt to save the output.

How do I sort a file and save it in place?
Use the -o option: sort -o file.txt file.txt. Unlike > file.txt, the -o option is safe to use with the same input and output file.

How do I sort by the last column?
Use a negative field number with the -k option: sort -k-1 sorts by the last field. Alternatively, use awk to reorder columns before sorting.

What is the difference between sort -u and sort | uniq?
sort -u is slightly more efficient as it removes duplicates during sorting. sort | uniq is more flexible because uniq supports options like -c (count occurrences) and -d (show only duplicates).

How do I sort lines randomly?
Use sort -R (random sort) or the shuf command: shuf file.txt. Both produce a random permutation of the input lines.

Conclusion #

The sort command is a versatile tool for ordering lines of text in files or command output. It is most powerful when combined with other commands like grep , cut , and head in pipelines.

If you have any questions, feel free to leave a comment below.

原理：

1. 使用位运算思想
2. 假设n=3
   • n=1 二进制为1
   • n=2 二进制为10
   • n=3 二进制为11

假设res为最终结果值，我们一般会想到先将1-n的二进制字符串都求出来然后拼接，再转为十进制，比较暴力。

但其实有更简单的算法，因为，拼接的结果无非是res二进制向左移 $x_i$ 位得到的值与所拼接二进制字符串值的和。
因此，事实上，$x_i$ 的值便是求解的关键。

容易看出，$x_i$ 即为值i表示的二进制字符串的位数，如何求得二进制字符串的位数呢？
类比于十进制，10的整数次幂所表示的值的10进制位数刚好差距为1，如$10^0$，$10^1$，$10^2$，$10^3$
类似的，$2^0$，$2^1$，$2^2$，$2^3$所表示的二进制的位数也刚好差距为1
我们可以利用这一点来求解。
如以n=3为例：
n=1时，二进制为1，res向左移动1位，与1相加，res值为1；
n=2时，二进制为10，res向左移动2位，与2相加，res值为6；
n=3时，二进制为11，res向左移动2位，与3相加，res值为27.

因此，我们只需要判断当前n值是否为为2的幂，如果是，位数偏移在之前的基础上加1，否则位数偏移不变
判断n值是否为2的幂方法有很多，在这里我采用了一种比较简单的方法i & (i-1)是否等于0，如果i是2的幂，说明仅某一位为1，其余均为0，那么i-1即为其余位均为1，自然与运算为0。如果难以理解可以想象99和100的关系。

下面是全部代码：

###java

public class Solution {
    private static final int MOD = 1000000007;

    public int concatenatedBinary(int n) {
        int res = 0, shift = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                // 说明是2的幂，则进位
                shift++;
            }
            res = (int) ((((long) res << shift) + i) % MOD);
        }
        return res;
    }
}

用位运算模拟这个过程：每拼接一个数 $i$，就把之前拼接过的数左移 $i$ 的二进制长度，然后加上 $i$。

由于左移后空出的位置全为 $0$，加法运算也可以写成或运算。

###go

func concatenatedBinary(n int) (ans int) {
    for i := 1; i <= n; i++ {
        ans = (ans<<bits.Len(uint(i)) | i) % (1e9 + 7)
    }
    return
}

方法一：模拟

思路与算法

由于我们需要将「十进制转换成二进制」「进行运算」「将结果转换回十进制」这三个步骤，因此我们不妨直接将整个问题在十进制的角度下进行考虑。

假设我们当前处理到了数字 $i$，并且前面 $[1, i-1]$ 的二进制连接起来对应的十进制数为 $x$，那么我们如何将数字 $i$ 进行连接呢？

观察二进制连接的过程，我们可以将这一步运算抽象为两个步骤：

• 第一步会将之前 $[1, i-1]$ 的二进制数左移若干位，这个位数就是 $i$ 的二进制表示的位数；

• 第二步将 $i$ 通过加法运算与左移的结果进行相加。

将上面所有的运算转换为 $10$ 进制，我们就可以得到 $x$ 的递推式，即：

$$
x = x \cdot 2^{\textit{len}_2(i)} + i
$$

其中 $\textit{len}_2(i)$ 就表示 $i$ 的二进制表示的位数，它可以通过很多语言自带的 API 很方便地计算出来。但我们还可以想一想如何通过简单的位运算得到 $\textit{len}_2(i)$。

我们可以这样想：由于 $len_2(i-1)$ 和 $len_2(i)$ 要么相等，要么相差 $1$（在二进制数发生进位时），因此我们可以使用递推的方法，在枚举 $i$ 进行上述运算的过程中，同时计算 $\textit{len}_2(i)$。如果 $len_2(i-1)$ 和 $len_2(i)$ 相差 $1$，那么说明 $i$ 恰好是 $2$ 的整数次幂，问题就变成了如何判断 $i$ 是不是 $2$ 的整数次幂，这就有两种常用的方法了：

• 第一种是找出一个比任何数都大的 $2$ 的整数次幂，比如本题中由于 $n \leq 10^5$，因此我们可以使用 $2^{17}=131072$，那么只要 $131072 ~%~ i = 0$，那么 $i$ 就是 $2$ 的整数次幂。

• 第二种是使用位运算，由于 $2$ 的整数次幂的二进制表示形如 $(1)_2$ 或者 $(10\cdots0)_2$ 的形式，将其减去 $1$ 是形如 $(0)_2$ 或者 $(01\cdots1)_2$ 的形式，恰好就是将减去 $1$ 之前的二进制表示翻转之后的结果，因此如果 $i ~&~ (i-1) = 0$，即 $i$ 和 $i-1$ 的二进制表示中没有某一位均为 $1$，那么 $i$ 就是 $2$ 的整数次幂。

通过上面的方法，我们就可以 $O(1)$ 地计算出 $\textit{len}_2(i)$ 了。

代码

###C++

class Solution {
private:
    static constexpr int mod = 1000000007;
    
public:
    int concatenatedBinary(int n) {
        // 
        int ans = 0;
        int shift = 0;
        for (int i = 1; i <= n; ++i) {
            // if (131072 % i == 0) {
            if (!(i & (i - 1))) {
                ++shift;
            }
            ans = ((static_cast<long long>(ans) << shift) + i) % mod;
        }
        return ans;
    }
};

###Python

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        mod = 10**9 + 7
        # ans 表示答案，shift 表示 len_{2}(i)
        ans = shift = 0
        for i in range(1, n + 1):
            # if 131072 % i == 0:
            if (i & (i - 1)) == 0:
                shift += 1
            ans = ((ans << shift) + i) % mod
        return ans

复杂度分析

• 时间复杂度：$O(n)$。

• 空间复杂度：$O(1)$。

方法二：数学

前言

看不懂也没关系。

思路与算法

设 $[a-t, a]$ 的二进制表示的位数均为 $k$，那么这一部分的和就为：

$$
S = a + (a - 1) 2^k + (a - 2) 2^{2k} + \cdots + (a-t) 2^{tk}
$$

使用高中数学的数列差分求和知识可以解得：

$$
S = \cfrac{\cfrac{2^k(2^{tk}-1)}{2^k-1} + (a-t) 2^{(t+1)k} - a}{2^k - 1}
$$

由于 $k$ 比较小而 $a,t$ 比较大，因此我们可以用快速幂优化计算。令：

$$
\begin{cases}
u = 2^{tk} \
v = (2^k-1)^{-1} \
w = 2^{(t+1)k} \
\end{cases}
$$

其中 $t^{-1}$ 表示在 $t$ 在模 $10^9+7$ 意义下的乘法逆元。带入得：

$$
S = \left(2^k(u-1)v + (a-t)w - a\right)v
$$

在计算 $S$ 的同时需要维护后缀 $0$ 的个数。

代码

###Python

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        mod = 10**9 + 7
        zeroes = 0
        ans = 0
        for k in range(64, 1, -1):   # 任意 64 位无符号整数都可以秒出答案
            if (lb := 2 ** (k - 1)) <= n:
                t = n - lb
                u = pow(2, t * k, mod)
                v = pow(2 ** k - 1, mod - 2, mod)
                w = pow(2, (t + 1) * k, mod)
                x = pow(2, zeroes, mod)
                ans += (2 ** k * (u - 1) * v + (n - t) * w - n) * v * x % mod
                zeroes += (t + 1) * k
                n = lb - 1
        
        ans += pow(2, zeroes, mod)
        return ans % mod

复杂度分析

• 时间复杂度：$O(\log^2 n)$。

• 空间复杂度：$O(1)$。

^ 关注我，带你一起学GIS ^

ArcPy是什么？下面这是来自ESRI中文官网的原话。

❝

ArcPy 是 Python 站点包，用于以有用且实用的方式使用 Python 执行地理数据分析、数据转换、数据管理以及制图自动化。

ArcPy 主要用于核心 GIS 应用程序。 它是一个 Python 软件包，提供了一种方法来执行与地理数据分析、数据转换、数据管理和地图自动化相关的各种任务，并可使用 Python 访问大约 2,000 个地理处理工具。它需要 ArcGIS 产品才能使用，如  ArcGIS Pro、ArcGIS Server  或  ArcGIS Notebooks。可通过 ArcPy 自动执行重复性任务，创建自定义地理处理工作流并扩展 ArcGIS Pro 的功能。 包括访问行业领先的空间分析和空间机器学习算法。它用于处理本地计算机上的数据、执行分析以及使用 ArcGIS Pro 自动执行任务。

我的理解为ArcPy是ESRI公司开发的基于Python的GIS数据处理、转换、分析的脚本。

AcyPy源于ArcGIS 9.2中所采用的arcgisscripting模块，并且集成在ArcGIS 10中。此后，AcyPy一直集成在ArcGIS 10.x中，并跟随ArcGIS一起发布，笔者最早接触的版本为最经典的版本ArcGIS 10.2，这个版本估计现在仍然有许多的使用者。直到后来ArcGIS Pro问世，AcyPy便集成在ArcGIS Pro中。

ArcPy 提供了一种用于开发Python脚本的功能丰富的动态环境，同时提供每个函数、模块和类的代码实现和集成文档。

下面将以ArcGIS Pro中集成的ArcPy进行讲解。在ArcPy中，主要包含以下十大模块。

• Charts  (arcpy.charts)
• Data Access  (arcpy.da)
• Geocoding  (arcpy.geocoding)
• Image Analysis  (arcpy.ia)
• Mapping  (arcpy.mp)
• Metadata  (arcpy.metadata)
• Network Analyst  (arcpy.nax  and  arcpy.na)
• Sharing  (arcpy.sharing)
• Spatial Analyst  (arcpy.sa)
• Utility Network (arcpy.un)

这十大模块包含了GIS数据处理、转换、分析的各方面，在学习中，可针对各模块进行专项练习。

既然ArcPy基于Python解释器，那么想要运行ArcPy脚本，就需要安装Python环境，而这已经集成ArcGIS产品中了，在ArcGIS10.x中集成的是Python2，ArcGIS Pro中集成了Python3。

1. 导入ArcPy

ArcPy模块的导入非常简单，可直接通过import arcpy导入。

# Import arcpy
import arcpy

# Set the workspace environment and run Clip
arcpy.env.workspace = 'E://data//arcpy'
arcpy.analysis.Clip("polygon.shp", "clip_feat.shp", "E://data//arcpy//standby_clip")

2. 运行ArcPy

在Python窗口中写入以下代码。打开ArcGIS Pro软件，选择菜单栏视图View，点击Python window。借助Python窗口交互式控制台，可以通过Python解释程序直接在ArcGIS Pro中运行Python代码，而无需脚本文件。 可在该窗口中运行的Python代码包括单行代码，也包括复杂的多行代码块。在窗口中输入以下代码，按回车运行。

# Import system modules
import arcpy

# Set workspace
arcpy.env.workspace = "E://data//arcpy"

# Set local variables
in_features = "polygon.shp"
clip_features = "clip_feat.shp"
out_feature_class = "E://data//arcpy//standby_clip"

# Run Clip
# arcpy.analysis.Clip("polygon.shp", "clip_feat.shp", "E://data//arcpy//standby_clip", 1.25)
arcpy.analysis.Clip(in_features, clip_features, out_feature_class)

也可以使用编辑器写入以上代码，在命令行窗口中运行脚本。

3. 查看帮助

Python提供文档字符串功能。ArcPy中的函数和类在包文档中使用该方法。读取这些消息以及获取帮助的方法之一是运行Python提供的help命令。使用参数运行该命令会显示对象的调用签名和文档字符串。

import arcpy 
help(arcpy)

4. ArcPy 基本词汇

主要介绍了要理解ArcPy帮助需要掌握的一些词汇，具有模块、类、函数等。

5. ArcGIS API for Python

还有一个需要区分一下ArcPy和ArcGIS API for Python

ArcGIS API for Python 是为WebGIS而设计的。 它是一个为执行GIS可视化和分析、空间数据管理和GIS系统管理任务提供广泛功能的Python库。

既可以交互使用，也可以通过脚本使用，使其成为GIS专业人员的通用工具。ArcGIS API for Python随附于ArcGIS Pro，但也可以与ArcGIS Online或ArcGIS Enterprise配合使用。借助ArcGIS API for Python，您可以创建和操作GIS数据、执行空间分析、将地图和图层发布到Web等。 您可以使用托管在ArcGIS Online 或ArcGIS Enterprise上的GIS数据和服务，并使用Python创建Web应用程序。它用于管理和分析WebGIS数据、自动化管理任务以及创建Web地图和应用程序。

参考资料

• https://desktop.arcgis.com/zh-cn/arcmap/latest/analyze/python/importing-arcpy.htm#ESRI_SECTION1_5E64CCAB40C24B0DB1ED80EF96176F73
• https://pro.arcgis.com/zh-cn/pro-app/latest/arcpy/get-started/python-window.htm

❝

GIS之路-开发示例数据下载，请在公众号后台回复：vector

全国信息化工程师－GIS 应用水平考试资料，请在公众号后台回复：GIS考试

❝

GIS之路 公众号已经接入了智能 助手，可以在对话框进行提问，也可以直接搜索历史文章进行查看。

都看到这了，不要忘记点赞、收藏 + 关注 哦 ！

本号不定时更新有关 GIS开发 相关内容，欢迎关注 

GeoTools 开发合集（全）

OpenLayers 开发合集

GDAL 开发合集（全）

GIS之路公众号2025年度报告

GDAL 遥感影像数据读取-plus

地图海报生成项目定位方式修改

关于 PyQT5 和 GDAL 导入顺序引发程序崩溃的解决记录

关于浏览器无法进入断点的解决记录

小小声说一下GDAL的官方API接口

ArcGIS Pro 添加底图的方式

为什么每次打开 ArcGIS Pro 页面加载都如此缓慢？

GDAL 实现矢量数据转换处理（全）

国产版的Google Earth，吉林一号卫星App“共生地球”来了

日本欲打造“本土版”星链系统