2.6 in C 位置pからはじまるnビットを右端にセット。他はそのまま。
unsigned setbits(unsigned x, int p, int n){
//return (x & (~0 << n)) | (x >> (p+1-n)) & ~(~0 << n);
return x^((x^(x >> (p+1-n))) & ~(~0 << n));
}
最下位ビットを0番目とする。
戻り値の論理式は
X & MASK | Y & ~MASK = Y ^ ( (Y ^ X) & MASK )
から。
これは、各ビットに対して
MASK == 1 のとき、Y ^ ( Y ^ X ) = X
MASK == 0 のとき、Y ^ 0 = Y
なので成り立つ。同様にMASKをひっくり返すと
X & ~~MASK | Y & ~MASK = X ^ ( (X ^ Y) & ~MASK )
となる。
2.7 in C 位置pからはじまるnビットを反転。他はそのまま。
unsigned invert(unsigned x, int p, int n){
return x ^(~(~0 << n ) << p-n+1);
}
反転させたいビットを1にしたマスクを作って、XORをとってやればよい。
たとえば4ビット目から数えて3ビット分のマスクを作る場合、
11111111 全て1のビット列を用意し
11111000 3ビット左シフト
00000111 反転
00011100 4-3+1ビット左シフト
できた！
2.8 in C nビット右へ回転シフト
unsigned rightrot(unsigned x, int n){
int i = 0;
unsigned mask = ~(~0U >> 1);
for (; i<n;i++){
if(x & 1 == 1){
x = (x >> 1) | mask;
} else {
x = x >> 1;
}
}
return x;
}
語調と独立な実装を考えると、1ビットずつシフトさせる方法しか思いつかなかった。
1ビット回転右シフトするときには、最も右端のビットがぐるっとまわって左端に入る。
つまり最下位ビットが0の場合は普通にシフトすればよく、1となっているときは左端に1をいれてやる。
そのためには最上位ビットのみを1にしたビット列とORをとってやればよい。
ビット演算子はPythonもほぼ一緒みたいなので略。
2.4 in C
#include <stdio.h>
void squeeze(char s1[], char s2[]){
int i, j, k = 0;
for ( i = 0; s1[i] != '\0'; i++){
for (j = 0; s2[j] != '\0'; j++){
if (s1[i] == s2[j]) break;
}
if (s2[j] == '\0') s1[k++] = s1[i];
}
s1[k] = '\0';
}
int main(void){
char x[]="fjdfskalfjda";
char y[]="bcde";
squeeze(x,y);
printf("%s",x);
return 0;
}
2.4 in Python
def squeeze(s1,s2):
return ''.join([((c in s2 and [''])or [c])[0] for c in s1])
x = "abfjdksahfjdas"
y = "abcde"
print squeeze(x,y)
リストを文字のシーケンスに戻すには空列に join してやればよいのか。それにしてもこういうところでしゃれた文字列を思いつけないのが悲しいところだ。
1.24 in C
#include <stdio.h>
#define BUF_SIZE 1024
#define SIZE 128
int sp = 0;
char *stack = NULL;
int ssize = 0;
int is_empty(){
if (sp == 0){
return 1;
} else {
return 0;
}
}
void push(char c){
if ( sp >= ssize){
stack = realloc(stack,sizeof(char) * (ssize += SIZE));
}
stack[sp++] = c;
}
char pop(void){
if (sp == 0){
fprintf(stderr,"STACK IS EMPTY");
exit(0);
} else {
return stack[--sp];
}
}
void spit_stack(){
int i;
fprintf(stderr,"%d\n",sp);
while(!is_empty()){
fprintf(stderr,"unpaired %c was found\n",pop());
}
free(stack);
}
int find_pair(char c){
char c1,c2;
if (c == ')') c1 = '(';
else if (c == '}') c1 = '{';
else if (c == ']') c1 = '[';
if (is_empty()) {
fprintf(stderr,"unpaired %c was found\n",c);
exit(0);
} else if ((c2 = pop()) == c1){
return 1;
} else {
fprintf(stderr,"mismatch between %c and %c\n",c2,c);
exit(0);
}
}
int main(void){
char s[BUF_SIZE];
int i, j, len;
int comment1, comment2, quoted1, quoted2;
comment1 = comment2 = quoted1 = quoted2 = 0;
while (fgets(s,BUF_SIZE,stdin)){
for (i=0;i < strlen(s);i++){
if (quoted1){
if (s[i] == '\\') {
putchar(s[i]);
putchar(s[++i]);
} else if (s[i] == '\"'){
quoted1 = 0;
}
putchar(s[i]);
} else if (quoted2){
if (s[i] == '\\') {
putchar(s[i]);
putchar(s[++i]);
} else if (s[i] == '\''){
quoted2 = 0;
}
putchar(s[i]);
} else if(comment1) {
if (s[i] == '*' && s[i+1] == '/') {
comment1 = 0;
i++;
putchar('\n');
}
} else if(comment2) {
if (s[i] == '\n') {
comment2 = 0;
putchar('\n');
}
} else {
if (s[i] == '\"'){
quoted1 = 1;
putchar(s[i]);
} else if (s[i] == '\''){
quoted2 = 1;
putchar(s[i]);
} else if (s[i] == '/') {
if(s[i+1] == '*') {
comment1 = 1;
i++;
} else if (s[i+1] == '/') {
comment2 = 1;
i++;
} else {
putchar(s[i]);
}
} else if (s[i] == '(' || s[i] == '{' || s[i] == '['){
push(s[i]);
putchar(s[i]);
} else if (s[i] == ')' || s[i] == '}' || s[i] == ']'){
find_pair(s[i]);
putchar(s[i]);
} else {
putchar(s[i]);
}
}
}
}
if (is_empty() == 0){
spit_stack();
}
return 0;
}
こんなのになった。括弧の数の対応だけはとっているが、『基本的な構文エラーのチェック』よりかなり前の段階にいるなあ。Pythonがどうとかいう以前の問題なのでちょっと考えよう。
1.23 in C
#include <stdio.h>
#define BUF_SIZE 1024
int main(void){
char s[BUF_SIZE];
int i, j, len;
int comment1, comment2, quoted1, quoted2;
comment1 = comment2 = quoted1 = quoted2 = 0;
while (fgets(s,BUF_SIZE,stdin)){
for (i = 0; i< strlen(s); i++){
if (quoted1){
if (s[i] == '\\') {
putchar(s[i]);
putchar(s[++i]);
} else if (s[i] == '\"'){
quoted1 = 0;
}
putchar(s[i]);
} else if (quoted2){
if (s[i] == '\\') {
putchar(s[i]);
putchar(s[++i]);
} else if (s[i] == '\''){
quoted2 = 0;
}
putchar(s[i]);
} else if(comment1) {
if (s[i] == '*' && s[i+1] == '/') {
comment1 = 0;
i++;
putchar('\n');
}
} else if(comment2) {
if (s[i] == '\n') {
comment2 = 0;
putchar('\n');
}
} else {
if (s[i] == '\"'){
quoted1 = 1;
putchar(s[i]);
} else if (s[i] == '\''){
quoted2 = 1;
putchar(s[i]);
} else if (s[i] == '/') {
if(s[i+1] == '*') {
comment1 = 1;
i++;
} else if (s[i+1] == '/') {
comment2 = 1;
i++;
} else {
putchar(s[i]);
}
} else {
putchar(s[i]);
}
}
}
}
return 0;
}
1.23 in Python
def linefind(s,t): #searching symbol "t" expected to be forward of a linefeed
p = s.find(t)
eol = s.find('\n') #if '\n' isn't found, eol = -1
if eol == -1 or p <= eol:
return p
else:
return -1
def commentDeleter(p):
quote3 = 0;
s=''
i=0
while(i < len(p)):
if p[i] == '"':
t = linefind(p[i+1:],'"')
if t == -1: #can't find pairing '"'
raise 'syntax error ---string must be closed with double quotation'
else:
s += p[i:i+t+2] #add "string..."
i = i + t + 2 #2 means ""itself
elif p[i] == "'":
t = linefind(p[i+1:],"'")
if t == -1: #can't find pairing "'"
raise 'syntax error ---string must be closed with quotation'
else:
s += p[i:i+t+2] #add 'string...'
i = i + t + 2 #2 means ''itself
elif i+2 < len(p) and p[i] == '"' and p[i+1] == '"' and p[i+2] == '"':
t = p[i+3:].find('"""')
if t == -1:
raise 'syntax error ---string must be closed with """'
else:
s += p[i:i+t+6] #add """string..."""
i = i + t + 6 #6 means ""","""
elif p[i] == '#':
t = linefind(p[i+1:],'\n')
s += '\n'
i = i + t + 2 #2 means # and '\n'
else:
s += p[i]
i += 1
return s
Python版はPythonのコメントを削除する……ハズ。findは見つからなかったときNoneではなくて -1 を返すのか。正規表現とか使えばもっとスマートになるんだろうか。
問題の意味がわからない。『入力のn文字目までにある最後の非ブランク文字の後で"折りたたむ"』というのはどいういこっちゃ。
こんな感じになればいいんだろうか？
1.22 in C
#include <stdio.h>
#define BUF_SIZE 1024
#define TURN_SIZE 10
int main(void){
char s[BUF_SIZE];
int i, j, len;
int last, space;
while (fgets(s,BUF_SIZE,stdin)){
last = space = 0;
for (i=0;i < strlen(s);i++){
if (s[i] == ' ') space++;
else {
if (last + space >= TURN_SIZE) {
putchar('\n');
last=0;
} else {
for (j = 0;j < space;j++){
putchar(' ');
}
last+=space;
}
space=0;
putchar(s[i]);
last++;
}
}
}
return 0;
}
1.22 in Python?
def eraceSpace(line):
i=0
while line[i] == ' ' and i < len(line)-1:
i += 1
line = line[i:]
i = len(line)-1
while line[i] == ' ' and i >= 0:
i -= 1
line = line[:i]
return line
TURNSIZE=10
s=raw_input()
last = 0
space = 0
i = 0
for i in range(0,len(s),TURNSIZE):
line = s[i:i+TURNSIZE]
line = eraceSpace(line)
print line
最初からn文字ずつに区切っちゃえばいいんじゃね？と思ったけどぜんぜん違ったヽ(`Д´)ﾉ行の頭にくるたびに文字を数えなおさなきゃいけないんだなー。
1.22 in Python
def eraceSpace(line):
i = len(line)-1
while i >= 0 and line[i] == ' ':
i -= 1
line = line[:i+1]
return line
TURNSIZE = 10
s = raw_input()
start = 0
last = TURNSIZE
end = len(s)
while start < end:
line = s[start:last]
print eraceSpace(line)
start = last
while start < end and s[start] == ' ':
start +=1
last = start + TURNSIZEこんな感じ？
1.21 in C
#include <stdio.h>
#define BUF_SIZE 1024
#define TAB_SIZE 5
int main(void){
char s[BUF_SIZE];
int i, j, len;
int space=0;
while (fgets(s,BUF_SIZE,stdin)){
for (i=0;i < strlen(s);i++){
if (s[i] == ' '){
space++;
if (space == TAB_SIZE){
putchar('\t');
space=0;
}
}else{
for(j=0;j<space;j++) putchar(' ');
space=0;
putchar(s[i]);
}
}
}
return 0;
}
1.21 in Python
TABSIZE = 5
s = raw_input()
s = s.replace(' ' * TABSIZE, '\t')
print s
1.20とreplaceの引数を逆にしただけ。
K&Rに載ってる問題をPythonでやってみようと思う。PyJUGでやっているのがソフトウェア作法だったのでインスパイヤしました。復習もかねてCでも書いてみる。
1.20 in C
#include <stdio.h>
#define BUF_SIZE 1024
#define TAB_SIZE 5
int main(void){
char s[BUF_SIZE];
int i, j, len;
while (fgets(s, BUF_SIZE,stdin)){
for (i=0;i < strlen(s);i++){
if (s[i] == '\t'){
for(j = 0;j < TAB_SIZE;j++){
putchar(' ');
}
}else{
putchar(s[i]);
}
}
}
return 0;
}
getstringはEOFまでの改行を含む文字列の入力を受け取り、その長さを返す。cygwinだと挙動がなんかおかしいぞ、と思って海外のサイトを見ると、EOFを入力するにはCtrl-Dを二回か空白行の頭でCtrl-Dを押せと書いてあった。これは仕様なんだろうか。
1.20 in Python
TABSIZE = 5
s = raw_input()
s = string.replace('\t', ' ' * TABSIZE)
print s
raw_inputを使っているので一行の入力しか受け取れないが、改行が含まれててもreplaceでいけるはず。
