Решаем задачу: компьютерные шахматы и вес Хэмминга

Читать в полной версии →

Условия

Начинающий программист Денис решил написать первый проект — браузерную версию компьютерных шахмат. Сначала все шло отлично — Денис нарисовал доску, где каждая клетка соответствует биту, закрепил отдельные значения за фигурами и написал алгоритм, который следит за происходящим на доске, прописал серверную часть и попробовал запустить приложение.

Спустя некоторое время разработчик заметил, что алгоритм иногда неправильно интерпретирует его действия: после хода фигуры то исчезают с доски, то появляются в неожиданных местах. Почитав форумы, программист выяснил, что проблема может возникать из-за ошибок, которые приводят к потере данных (искажению битов) при передаче пакетов от сервера к клиенту.

Тогда Денис решил добавить функцию проверки потери данных — вес Хэмминга, который по определенной схеме перебирает все биты в пакете и указывает на тот, в котором произошло искажение.

Проблема в том, что Денис никогда не сталкивался с подобными функциями, и решил потренироваться на сравнительно простом примере прежде, чем решать стоящую перед ним задачу.

Условия примера звучат так:

Число Хэмминга количество единиц в двоичном представлении числа. Нужно реализовать функцию hammingWeight(), которая принимает целое число в качестве параметра и возвращает вес Хэмминга.

hammingWeight(0); // 0
hammingWeight(4); // 1
hammingWeight(101); // 4

Читайте также: Как сохранять фокус на протяжении всего обучения: советы от Хекслета

Решение

Эта задача — из испытаний базового курса по Java на Хекслете. С ней справились 89% наших студентов. Ниже опубликован разбор решения — вы можете сравнить свое решение с нашим или посмотреть реализацию, если самостоятельно решить задачу не удается.

Задачу можно решить на нескольких языках программирования например, на Java или PHP. Ниже опубликован вариант решения на Java, по которому можно воспроизвести определение веса Хемминга.

import java.util.Arrays;
import java.util.List;

public class HammingWeight {
    public static int hammingWeight(int value) {

        int weight = 0;
        List<String> digits = Arrays.asList(Integer.toBinaryString(value).split(""));
        for (String digit : digits) {
            if (digit.equals("1")) {
                weight += 1;
            }
        }
        return weight;
    }
}

О решении этой задачи на PHP на примере код-ревью одного из студентов Хекслета можно почитать здесь.

Никогда не останавливайтесь: В программировании говорят, что нужно постоянно учиться даже для того, чтобы просто находиться на месте. Развивайтесь с нами — на Хекслете есть сотни курсов по разработке на разных языках и технологиях