Codewars Java练习:Find the next perfect square!

题目

You might know some pretty large perfect squares. But what about the NEXT one?

Complete the findNextSquare method that finds the next integral perfect square after the one passed as a parameter. Recall that an integral perfect square is an integer n such that sqrt(n) is also an integer.

If the parameter is itself not a perfect square, than -1 should be returned. You may assume the parameter is positive.

Examples:

题解

Java的数学计算并没有内置到基本数据类型的成员函数中(否则int,long这类内置数据类型就没法参与运算了),而是集中到了Math包中。

将sq开方,并判断是否为整数,我的做法是把开方后的数强制转化为整形,然后平方检验。

当然,标准答案告诉我并不需要这么复杂,Java本身浮点数是支持取模运算,而对1取模可以用来判断是否是整数——

 

Codewars Java练习:Bit Counting

题目

Write a function that takes an (unsigned) integer as input, and returns the number of bits that are equal to one in the binary representation of that number.

Example: The binary representation of 1234 is 10011010010, so the function should return 5 in this case

题解

我使用了每次右移,统计奇偶性的解法——

标准解法中,我比较喜欢的有如下代码——

直接使用Integer的库函数

转换为字符串处理,其中用到了Java中的Lambda表达式

 

 

Codewars Java练习:Two to One

题目名称

TwoToOne

题目

Take 2 strings s1 and s2 including only letters from ato z. Return a new sorted string, the longest possible, containing distinct letters,

  • each taken only once – coming from s1 or s2.

Examples:

a = “xyaabbbccccdefww” b = “xxxxyyyyabklmopq”

longest(a, b) -> “abcdefklmopqwxy”

a = “abcdefghijklmnopqrstuvwxyz”

longest(a, a) -> “abcdefghijklmnopqrstuvwxyz”

题目大意

给定两个字符串,将其加起来,去重,排序后输出。

题解

刻意练习了一下ArrayList类似的容器的使用方式,发现这类问题通常有两个核心要点——

  • 如何将原始元素类型转化为对象形式,比如本题中如何将char数组和Character数组相互转换——
    • 事实上,这个转换在后期的Java版本中有ArrayUtils类提供转换函数
    • 而在早起的版本中,只有通过for语句逐个元素构造
  • 如何在内置数组、ArrayList之间转化
  • 如何在可重ArrayList和不可重的HashSet之间转化。

标准答案

最后欣赏一下标准答案——

代码使用了String的chars()函数,返回了一个IntStream类,这个类支持了后续的所有的过滤变换操作。

Codewars Java练习:Consecutive strings

题目

You are given an array strarr of strings and an integer k. Your task is to return the first longest string consisting of k consecutive strings taken in the array.

#Example:

longest_consec([“zone”, “abigail”, “theta”, “form”, “libe”, “zas”, “theta”, “abigail”], 2) –> “abigailtheta”

n being the length of the string array, if n = 0 or k > n or k <= 0 return “”.

题解

算是中规中矩的一道题吧

 

Java使用正则表达式实现重叠匹配

问题:在一篇文章中一个匹配日期 yyyy-MM-dd 的程序。

显然一个日期对应Java中的正则表达式

然而,这样的正则表达式实现方式在处理如下输入数据时,无法提取出重叠的匹配

结果

这是由于第一个匹配消耗了其所在的所有字符的缘故,后续匹配将无法使用这些字符。这是我们需要使用 (?=((\\d{4})-(\\d{2})-(\\d{2}))). 正则表达式。

其中 (?=X) 这个语法匹配一个“位置”,这个位置向后可以完全匹配正则表达式X。 (\\d{4})-(\\d{2})-(\\d{2}) 是之前用于匹配日期的正则表达式, . 用于匹配单个字符。整个正则表达式语义为“匹配一个可以匹配日期字符串的位置及其后的一个字符”。

而原来的年月日信息可以通过 groups() 函数得到——

对应的整个程序为——

 

一句话解析汇编中的ret和call指令

这篇文章有点标题党了,因为实际上这ret和call还真没法一句话说完,向下读之前,读者需要知道——

  • 什么是,栈的pop和push指的是什么
  • 初步了解了栈在函数调用中的作用

汇编中,函数调用是通过栈维护的,栈顶指针称为%rsp。通常有两类汇编命令能修改%rsp:

  • 一类是直接使用add和sub汇编指令,这种情况多用于函数在栈中分配零时空间直接通过对%rsp加减指定数值得到。
  • 另一类是pop和push汇编指令,该指令隐含了一个%rsp加一或减一的操作,多用于试图保存一个寄存器的值供后续恢复。

另一方面,有个程序运行指令的计数器%rip,时时刻刻指向下一条指令的内存位置。一般情况下,%rip都是一个一个加下去的,特例是使用了jmp指令,则%rip直接被赋值为jmp的目标地址。

当汇编指令call被调用的时候,首先会隐式调用一个push命令,将储存有“之后本应该执行的语句的地址<CALLBACK>”的寄存器%rip的值放到栈顶,然后一个jmp指令通过修改%rip,将程序指令流跳转到目标位置。

当汇编指令ret被调用的时候,首先会有一个pop命令,将栈顶的值<CALLBACK>弹出,并放在%rip中作为下一个需要执行的代码。

关于汇编中的函数调用,我在另一篇文章解析汇编中实现函数调用的若干方式中有更详细的阐述。

解析汇编中实现函数调用的若干方式

相同的c/c++语言的函数调用,在编译成汇编代码之后,会存在不同的解析方式,这些解析方式一方面依赖于编译器本身(比如gcc和g++编译出的代码就不尽相同),另一方面也会受到编译选项的影响(比如是否打开-O2 -fno-stack-protector这些编译开关)。网上很多其他的资料无视了实现函数调用的汇编代码的多样性,使得读者会在对照理解时出现一些困难。

在这篇文章中,我将通过几个小例子,介绍不同情况汇编实现C/C++语言函数调用的方式。具体的代码可以在 我的github 上面看到。


下图是一个简单的读入字符串的程序(注意,这个程序故意引入了不安全的gets函数)的C语言版本和C++版本——

 

这个程序中的getbuf函数就是我们今天讨论的主题

通过栈帧实现的函数调用

简单的例子

这是C语言代码版本通过编译命令 gcc c.c -o c -fno-stack-protector 生成的汇编代码——

理解%rsp和%rbp

其中两个重要的寄存器分别是 %rbp 和 %rsp , %rbp 称作帧指针,而 %rsp 称作栈指针。首先需要记住如下事实:

  • 函数的栈空间是从大地址空间向小地址空间生长。也就是说,在栈空间中的push操作会使 %rsp 越来越小。(对应右图中上面为高地址,下面为低地址)
  • 当前程序的局部变量储存在 %rsp 和 %rbp 两个指针所夹的那一段区域内(对应右图中紫色部分)

现在,在形式化定义 %rsp 和 %rbp :

%rsp 表示栈顶指针,永远指向当前使用栈空间中最下面的位置的地址。因此在我们的程序中,只用于定位栈顶的位置,并支持栈的插入弹出,而不用于地址索引。一般需要改变 %rsp 的地方有——

  • push指令:push指令将 %rsp 的值减一,并在新的 %rsp 位置放上需要push的值
  • pop指令:pop指令将 %rsp 的值加一,并将原来的 %rsp 位置上的值放在pop的寄存器中
  • 进入函数中,函数需要一定的空间,直接使用 sub $0x10,%rsp 分配整块的空间。
  • call指令和ret指令:其中内含了对于寄存器 %rip 的push和pop操作。关于call指令和ret指令更加详细的说明,在我的另一篇文章一句话解析汇编中的ret和call指令有更详细的解答。

%rbp 表示帧指针,一般在函数中用于定位,由于 %rsp 身兼多职,可能在一个函数块内修改,因此,给予 %rsp 的栈内信息定位是可行但不方便的。帧指针 %rbp 指向的位置是函数调用后,使用push操作保存上一个函数的帧指针后, %rsp 的位置,换句话说,这个位置就是没有进行任何局部变量分配是,栈顶 %rsp 的位置,之后的任何函数内的 %rsp 修改就都与 %rbp 无关了。从构造上来说, %rbp 还能用来实现函数的退出以及上一层函数的恢复。需要修改 %rbp 的地方有——

  • 调用函数时, %rbp 仍然指向的是上一层函数的帧,需要更新。为了之后可以恢复,需要将当前的 %rbp 的值使用push指令,放在栈顶,然后将 %rbp 赋值为 %rsp ,标记为“当前帧指针就是刚进入函数,没有分配任何内容的栈顶指针”。同时,新的 %rbp 指向的位置存有 %rbp 在函数退出时需要恢复的值。
  • 退出函数时,需要将%rbp更新回去。

汇编代码解读

回到之前的汇编代码,我们看看调用getbuf之后,究竟干了些啥:

整个getbuf的调用依次是——

  • 【位于main中】call指令,将程序结束下一条指令地址 %rip push至栈顶,并将call的函数入口地址赋值给 %rip ,实现指令流的跳转。
  • 保存旧的 %rbp 至栈顶,此时push使得 %rsp 加了1
  • 将栈顶指针 %rsp 赋值到 %rbp 中,此时新的 %rbp 可以理解成main函数内部变量和getbuf函数内部变量的分界线,而这个位置之后会作为getbuf函数内部变量定位的基准。
  • 函数内部变量需要使用接下来0x10大小的空间,在栈中预先分配
  • 我们将分配的那一块空间用来存buf数组,那么buf指针的值就应该是 %rbp-0x10 了
  • 将存有buf数组的寄存器 %rax 赋值给 %rdi
  • 将零时储存器 %rax 清零
  • 调用gets函数
  • 将储存器 %rax 赋值为1作为返回值
  • 使用leaveq指令恢复栈帧 %rbp
  • 使用ret指令将栈顶储存的“函数退出后下一条语句地址”弹出,并重定向为下一句执行位置。

C语言与C++语言

C++语言的getbuf函数汇编代码如下,可以发现,除了函数符号名有些区别外,没有其他的区别。

只使用栈指针实现函数调用

倘若在编译时,添加-O2优化,则C语言代码的getbuf部分变成了:

由于在之前的实现中, %rbp 的作用实际上是简化由于 %rsp 的变化导致定位偏移量不容易计算而设计出来的,如果我们成功追踪了 %rsp 在每个函数调用过程中的变化量,就很容易实现函数调用的恢复操作。

而在-O2优化下,编译器会以效率优先,如果我们完全知道了代码长什么样的,也知道每一次程序 %rsp 的变化量,实际上 %rbp 就不是那么有必要了。也就是说,这个程序是单纯使用 %rsp 实现函数调用的例子。

在上面程序中,getbuf调用步骤为:

  • 【main函数中】call指令调用getbuf,getbuf返回后下一条指令的地址被压栈,处理器指令运行的指针被置于getbuf其实位置
  • 移动 %rsp 分配足够空间
  • 清零 %eax
  • %rsp (即buf数组的地址),作为gets的参数,放在 %rdi 中
  • 调用gets函数
  • 将返回值放在 %eax 中
  • 将之前 %rsp 分配空间部分撤销
  • 退出

函数调用中的参数传递

尝试将原来的程序中,添加参数传入,得到下面的getbuf函数——

函数中传入了一大堆参数,这时因为,C++在传入参数少和传入参数多的时候,处理方式有所区别,因此,只有当 getbuf 函数传入足够多的参数时,才能成功涵盖两种方式。

将上述代码编译之后,得到汇编代码如下——

以及调用者main函数的反汇编代码。

 

可以发现,对于参数的传递,分为两种方式——

  • 当参数个数本身较少的时候,直接使用寄存器传参。对应了0x4005e6-0x400601的代码
  • 当参数个数比较多的话,无法用寄存器装下的参数,在调用前压到栈里面,由被调用者通过 %rbp 定位取之,在调用完成后,被调用者再将压栈的参数弹出。

在细节上,对于寄存器传参,依次使用了寄存器 %rdi , %rsi , %rdx , %rcx , %r8 , %r9 ;对于压栈传参,是按照参数位置,从右到左压栈。

包含金丝雀保护机制的函数调用

倘若编译参数中,没有 -fno-stack-protector,则C语言的getbuf编译出来如下——

多出来的一部分代码被称为金丝雀,是防止gets操作产生危险后果的,具体原理有时间再更~

环境与配置

gcc版本 (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609

g++版本 (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609

Ubuntu版本 16.04 64位

天龙八部——与生活在不经意间的互动

天龙八部的名字很早之前就已经听说了,不过真正打算读是在大学老师一次以珍珑棋局打比方,感觉很有意思,于是就开始读。结果这本书的长度还真超出了我的想象,前前后后花了半年的时间才读完。只是随手写写自己的观感,可能不能算是书评吧。

这本书继承了金庸的一贯风格,在描绘了一朝武林的一个非常宏达的设定的同时,还能细致入微,细数男男女女之事,甚至在写男女之情方面超越了部分专门的爱情小说。借武侠之名写生活中的细小之事,给人以强烈的共鸣。

金庸的武侠小说厉害之处情节平平淡淡,你说设计精巧吧,其实也不至于。但是读了这个文章,我们总能悟到一些东西,这也是为什么我会从大学老师口中听到珍珑棋局这个典故,进而读到这一本书。有时候,我们还能从书中的情节,找到现实生活中的一些影子,以近期的热点事件“谷歌回归中国”为例,在网上,我读到了一个非常有意思的用《天龙八部》类比谷歌百度的文章——

曾几何时,但凡中原武林人士,只要听到“北乔峰,南慕容”这响当当的名头,都是要翘一翘大拇指的。

偌大一个江湖,被公认为大英雄的只有这么两个人,还不够嘚瑟的?

有好事的就要问了,那这乔峰和慕容复,到底谁更厉害呢?

这个不太好说,因为后来中原只剩下了一个南慕容。

北乔峰呢?被赶走啦!

赶他走的理由是天经地义的:他是个契丹人啊!

这可是个非常严肃的问题。契丹和我大宋正在打仗呢,我们两国人民势不两立。燕云十六州也被辽国占了,我们中原正统的面子上相当过不去。大家都说契丹夷种十分野蛮,欺男霸女无恶不作。这样的人,怎么能在我中原武林立足?

你要仅仅是家庭成分不好也就罢了,哪怕偷鸡摸狗品行不端也没关系,就算是个铁头怪物大家也能接受,但谁叫你好死不死偏偏是个契丹狗种呢?

你看,徐长老都说了:“非我族类,其心必异。”徐长老在丐帮里德高望重,他说的一定没错的。

全冠清也大声呼吁:“大家都是精忠报国的好汉,难道甘心为异族的奴隶走狗么?”这小白脸正气凛然,一定不会骗人的。

连聚贤庄主游氏兄弟都表态要“扑杀番狗”了,鲍千灵和向望海这样的小角色都懂得谴责契丹夷种“假仁假义”了,大家还有什么理由不跟上呢?就算只是像追魂杖谭青那样,躲在人丛中地用腹语骂上几句,也是很过瘾的嘛。虽然他是“恶贯满盈”的弟子,平时也很为大家所不齿,但毕竟还是人民内部矛盾嘛,面对外敌,还是要统一战线的。

于是众人纷纷表态:“一个人就算再不成器,也决计不愿做汉奸卖国贼。”

大家同仇敌忾,终于把乔峰赶回了大辽,去当他的劳什子南院大王去了。祛除了这个祸胎,中原武林过上了好几年的太平日子。

没有了竞争对手,慕容氏不断坐大,逐渐有了称霸武林、独孤求败的气势。只要是个练家子,就没有不知道慕容复大名的,一招“斗转星移”,令多少武术名家骇然变色。

慕容复自己想必也很得意,什么北乔峰,也只能在国境外逞逞威风,有本事踏进长城一步吗?

但是渐渐的,外面有了一些闲言碎语。

有人说,以彼之道,还施彼身,这就是赤裸裸的山寨啊!不管自创出个啥武功,马上就被你抄袭去了,这还怎么玩啊。姑苏慕容简直成了武林后辈成长路上一道无法绕开的屏障。

有人说,慕容复武功虽高,但人品不好,经常鼓捣些悲酥清风之类的三无药品,不知道害了多少人。

还有人说,当年聚贤庄赶走乔峰的那场恶战,慕容复可并不在场。对比慕容家如今赢得的势力,似乎赢得有点不太光彩。

慕容复也是有自尊心的,他也想证明自己啊。

机会还是来了。乔峰更名萧峰,回到中原,和众豪杰在少林寺狭路相逢。

慕容复一来形格势禁,地位摆在这,该你上还是得上,二来为“收揽人心,以为己助”,三来仗着有丁春秋和游坦之助拳,似乎立于不败之地,于是不失时机地站出来说道:

“萧兄,你是契丹英雄,视我中原豪杰有如无物,区区姑苏慕容复今日想领教阁下高招。在下死在萧兄掌下,也算是为中原豪杰尽了一份微力,虽死犹荣。”

中国人礼节为先,说话含蓄,讲究听话听音。这段话看似平平无奇,其实言外之意很多,翻译出来大概是:

你丫现在回来了,但中原武林现在蓬勃发展,而且我已经是当之无愧的老大了。大家都说是因为你出国了我才成为老大的,其实在你走的时候已经有七成武林人士支持我了。我非常有信心真刀真枪再PK一次,再赢一次。

围观群众们听得热血沸腾,一片喝彩,skr skr skr。

当然有见过世面的,比如王语嫣,此时就开始担心了。从小到大只见过表哥打拳,当然以为他就是全天下最厉害的人物,直到当年在杏子林里见识了乔峰的一招“擒龙功”,王语嫣的人生观便被彻底颠覆:“这位乔帮主武功如此了得,我表哥跟他齐名,江湖上有道是’北乔峰,南慕容’,可是……可是我表哥的武功,怎能……怎能……”

此后的事实证明了王语嫣的担忧。慕容复和丁春秋、游坦之一起三打一,也没能占到上风,反而被萧峰一把抓住后心“神道穴”,提在半空,“其势直如老鹰捉小鸡一般”,又被萧峰手臂一振,直飞出七八丈外,“砰的一声,背脊着地,只摔得狼狈不堪。”

萧峰还说了句风凉话:

“萧某大好男儿,竟和你这种人齐名!”

最后,慕容复的爸爸慕容博从天而降,才没让慕容复血溅当场。

时至此刻,丐帮群雄、少林僧侣、各门各派的围观群众才终于弄明白了两件事情:

第一,原来南慕容和北乔峰之间的差距居然如此之大;

第二,当年逼走乔峰的幕后操盘手,原来不是别人,正是你慕容家的老爹啊!拿国仇家恨民族感情忽悠我们,其实还不是你们自己想当老大!

于是乎“噫”地一声,群众们一哄而散。

实在无法想象,如此精准的语言,在没有经历的时候,还真就觉得是一个平平淡淡的情节设定而已,最终没有想到竟然预言得如此精准!
小说分为若干条故事线,粗略谈谈自己的看法——
首先是段誉线,网上很多文章都调侃说是“真·泡妹”,“愿有情人终成兄妹”,“德国骨科发源地”啥的。说实话,作者在这里挺恶趣味的,我追一个妹子,亲妹妹……在追一个,亲妹妹……再追……这是一个悲伤的故事。可以说,段誉以身都没有走出放荡的父亲留下的阴影。个人还是不太能够理解作者设定这个人物更加深层次的用心。也许是为了刻画一种情绪的大喜大落,也可能只是为了可以构造喜剧情节而已(对于人物本身来说是悲剧_(:з」∠)_)。
其次是萧峰线,萧峰和阿朱的故事真的非常有吸引力,不过从另一方面说,不论是这里的阿朱,还是射雕里面的黄蓉,金庸笔下的“主角女性”感觉都是从一个模子里面刻出来的一样,机灵,幽默,体贴……不过,既然我最喜欢的性格,我一点意见也没有。可惜阿朱在中途离开了,转而代替她的阿紫却是一个在性格上比较反面的设定,由于我的阅读进度拉的挺长的,因此对于阿朱的记忆已经模糊至此,没有更多详细的理解了。
虚竹线中,开局小兵,一路开挂登顶。他的故事,就是标准的好人有好报的喜剧故事,其中最打动我的,是梦姑梦郎相见的场景,而这个场景的笔墨描写只是寥寥几句,却胜过千言万语。
那宫女道:“先生尊姓大名?”
虚竹道:“我么……我么……我道号虚竹子。我是……出……出……那个……决不是来求亲的,不过陪着我三弟来而已。”
那宫女问道:“先生平生在甚么地方最是快乐?”
虚竹轻叹一声,说道:“在一个黑暗的冰窖之中。”
忽听得一个女子声音“啊”的一声低呼,跟着呛啷一声响,一只瓷杯掉到地下,打得粉碎。
那宫女又问:“先生生平最爱之人,叫甚么名字?”
虚竹道:“唉!我……我不知道那位姑娘叫甚么名字。”
众人都哈哈大笑起来,均想此人是个大傻瓜,不知对方姓名,便倾心相爱。
那宫女道:“不知那位姑娘的姓名,那也不是奇事。当年孝子董永见到天上仙女下凡,并不知她的姓名底细,就爱上了她。虚竹子先生,这位姑娘的容貌定然是美丽非凡了?”
虚竹道:“她容貌如何,我也是从来没看见过。”
霎时之间,石室中笑声雷动,都觉真是天下奇闻,也有人以为虚竹是故意说笑。众人哄笑声中,忽听得一个女子声音低低问道:“你……你可是‘梦郎’么?”
虚竹大吃一惊,颤声道:“你……你……你可是‘梦姑’么?这可想死我了。”
不由自主的向前跨了几步,只闻到一阵馨香,一只温软柔滑的手掌已握住了他手,一个熟悉的声音在他耳边悄声道:“梦郎,我便是找你不到,这才请父皇贴下榜文,邀你到来。”
虚竹更是惊讶,道:“你……你便是……”
那少女道:“咱们到里面说话去,梦郎,我日日夜夜,就盼有此时此刻……”
一面细声低语,一面握着他手,悄没声的穿过帷幕,踏着厚厚的地毯,走向内堂。
石室内众人兀自喧笑不止。
读到这里,我才意识到本以为前面平淡的文字并没有对我产生触动,但是并不是这样的——一切的铺垫都为了最后的爆发!而这个爆发奠定了虚竹作为全书中最浪漫,最理想化的一个人物的存在。
最后是慕容复线,这个“蹭热度狂魔”确实最终下场悲惨,有绝世美人在旁,却沉迷于帝王江山梦,是标准的欲望太大最终一无所得。对比段誉,确实苦苦追求直到耗尽青春的冲动。慕容复算是一个反面任务吧。
主线之外,还有一些其他的很有意思的配角,这里引用在b站av20938194视频下的一条很有意思的评论概括,生动形象~

关于天龙八部的说法:

乔峰开局就满级,段誉中途开挂,虚竹盗满级号,慕容复前期充钱,得充值礼包就到处浪,只顾搞公会,后期都没满级,只有鸠摩智是一刀一刀砍怪升级。由于前期欺负段誉,后期被段誉开挂复仇,丢装备删号退服。萧远山和慕容伯卡bug升级,最后在公屏上对骂,互相举报,被GM扫地僧给封号了,游坦之是捡了别人爆的极品装备咯,王语嫣是任务说明NPC。

可能文学最令人激动地一点就是能够与生活在不经意间互动吧。

Latex平衡双栏引用的两栏高度

最近投论文,要求全文双栏,我使用了默认的 \bibliography

结果如图

主办方工作人员非常nice地告知需要平衡两栏长度,并且提供了详细的解决方案

  • 如果是使用普通方法手打引用的话,可以使用 \vfill\eject 命令分割需要换栏的位置。
  • 如果使用 \bibliography 生成引用的话,可以先  \usepackage{balance} ,然后在  \bibliographystyle 和 \bibliographystyle 之间加一句  \balance 。

改后引用页面如下——