diff options
Diffstat (limited to 'exercises')
| -rw-r--r-- | exercises/096_memory_allocation.zig | 1 | ||||
| -rw-r--r-- | exercises/097_bit_manipulation.zig | 95 | ||||
| -rw-r--r-- | exercises/098_bit_manipulation2.zig | 64 |
3 files changed, 160 insertions, 0 deletions
diff --git a/exercises/096_memory_allocation.zig b/exercises/096_memory_allocation.zig index d490fdb..4a89702 100644 --- a/exercises/096_memory_allocation.zig +++ b/exercises/096_memory_allocation.zig @@ -1,3 +1,4 @@ +// // In most of the examples so far, the inputs are known at compile // time, thus the amount of memory used by the program is fixed. // However, if responding to input whose size is not known at compile diff --git a/exercises/097_bit_manipulation.zig b/exercises/097_bit_manipulation.zig new file mode 100644 index 0000000..38f2a86 --- /dev/null +++ b/exercises/097_bit_manipulation.zig @@ -0,0 +1,95 @@ +// +// Bit manipulations is a very powerful tool just also from Zig. +// Since the dawn of the computer age, numerous algorithms have been +// developed that solve tasks solely by moving, setting, or logically +// combining bits. +// +// Zig also uses direct bit manipulation in its standard library for +// functions where possible. And it is often possible with calculations +// based on integers. +// +// Often it is not easy to understand at first glance what exactly these +// algorithms do when only "numbers" in memory areas change outwardly. +// But it must never be forgotten that the numbers only represent the +// interpretation of the bit sequences. +// +// Quasi the reversed case we have otherwise, namely that we represent +// numbers in bit sequences. +// +// We remember: 1 byte = 8 bits = 11111111 = 255 decimal = FF hex. +// +// Zig provides all the necessary functions to change the bits inside +// a variable. It is distinguished whether the bit change leads to an +// overflow or not.The details are in the Zig documentation in section +// 10.1 "Table of Operators". +// +// Here are some examples of how the bits of variables can be changed: +// +// const numOne: u8 = 15; // = 0000 1111 +// const numTwo: u8 = 245; // = 1111 0101 +// +// const res1 = numOne >> 4; // = 0000 0000 - shift right +// const res2 = numOne << 4; // = 1111 0000 - shift left +// const res3 = numOne & numTwo; // = 0000 0101 - and +// const res4 = numOne | numTwo; // = 1111 1111 - or +// const res5 = numOne ^ numTwo; // = 1111 1010 - xor +// +// +// To familiarize ourselves with bit manipulation, we start with a simple +// but often underestimated function and then add other exercises in +// loose order. +// +// The following text contains excerpts from Wikipedia. +// +// Swap +// In computer programming, the act of swapping two variables refers to +// mutually exchanging the values of the variables. Usually, this is +// done with the data in memory. For example, in a program, two variables +// may be defined thus (in pseudocode): +// +// data_item x := 1 +// data_item y := 0 +// +// swap (x, y); +// +// After swap() is performed, x will contain the value 0 and y will +// contain 1; their values have been exchanged. The simplest and probably +// most widely used method to swap two variables is to use a third temporary +// variable: +// +// define swap (x, y) +// temp := x +// x := y +// y := temp +// +// However, with integers we can also achieve the swap function simply by +// bit manipulation. To do this, the variables are mutually linked with xor +// and the result is the same. + +const std = @import("std"); +const print = std.debug.print; + +pub fn main() !void { + + // As in the example above, we use 1 and 0 as values for x and y + var x: u8 = 1; + var y: u8 = 0; + + // Now we swap the values of the two variables by doing xor on them + x ^= y; + y ^= x; + + // What must be written here? + ???; + + print("x = {d}; y = {d}\n", .{ x, y }); +} + +// This variable swap takes advantage of the fact that the value resulting +// from the xor of two values contains both of these values. +// This circumstance was (and still is) sometimes used for encryption. +// Value XOR Key = Crypto. => Crypto XOR Key = Value. +// Since this can be swapped arbitrarily, you can swap two variables in this way. +// +// For Crypto it is better not to use this, but in sorting algorithms like +// Bubble Sort it works very well. diff --git a/exercises/098_bit_manipulation2.zig b/exercises/098_bit_manipulation2.zig new file mode 100644 index 0000000..d5ee825 --- /dev/null +++ b/exercises/098_bit_manipulation2.zig @@ -0,0 +1,64 @@ +// +// Another useful practice for bit manipulation is setting bits as flags. +// This is especially useful when processing lists of something and storing +// the states of the entries, e.g. a list of numbers and for each prime +// number a flag is set. +// +// As an example, let's take the Pangram exercise from Exercism: +// https://exercism.org/tracks/zig/exercises/pangram +// +// A pangram is a sentence using every letter of the alphabet at least once. +// It is case insensitive, so it doesn't matter if a letter is lower-case +// or upper-case. The best known English pangram is: +// +// "The quick brown fox jumps over the lazy dog." +// +// There are several ways to select the letters that appear in the pangram +// (and it doesn't matter if they appear once or several times). +// +// For example, you could take an array of bool and set the value to 'true' +// for each letter in the order of the alphabet (a=0; b=1; etc.) found in +// the sentence. However, this is neither memory efficient nor particularly +// fast. Instead we take a simpler way, very similar in principle, we define +// a variable with at least 26 bits (e.g. u32) and also set the bit for each +// letter found at the corresponding position. +// +// Zig provides functions for this in the standard library, but we prefer to +// solve it without these extras, after all we want to learn something. +// +const std = @import("std"); +const ascii = std.ascii; +const print = std.debug.print; + +pub fn main() !void { + // let's check the pangram + print("Is this a pangram? {?}!\n", .{isPangram("The quick brown fox jumps over the lazy dog.")}); +} + +fn isPangram(str: []const u8) bool { + // first we check if the string has at least 26 characters + if (str.len < 26) return false; + + // we uses a 32 bit variable of which we need 26 bit + var bits: u32 = 0; + + // loop about all characters in the string + for (str) |c| { + // if the character is an alphabetical character + if (ascii.isASCII(c) and ascii.isAlphabetic(c)) { + // then we set the bit at the position + // + // to do this, we use a little trick: + // since the letters in the ASCI table start at 65 + // and are numbered by, we simply subtract the first + // letter (in this case the 'a') from the character + // found, and thus get the position of the desired bit + bits |= @as(u32, 1) << @truncate(u5, ascii.toLower(c) - 'a'); + } + } + // last we return the comparison if all 26 bits are set, + // and if so, we know the given string is a pangram + // + // but what do we have to compare? + return bits == 0x..???; +} |